Introduction

Simulation based calibration (SBC) can be used to validate inference algorithms by repeated inference given repeated simulated data from a generative model. The original and commonly used approach generated the generative model parameters from prior, and thus the approach is testing whether inference works for simulated data generated with parameter values plausible under that prior. This is natural and desirable when we want to test whether the inference works for for many different types of data sets we might observe. After observing data, we are interested whether the inference did work conditional on that data, and the posterior given the observed data is often much more concentrated than the prior. Here we demonstrate how SBC can be used conditionally on observed data.

Simulation based calibration

Cook, Gelman and Rubin (2006) proposed a simulation-based calibration method for validating Bayesian inference software. The idea is based on the fact we can factor the joint distribution of data \(y\) and parameters \(\theta\) in two ways \[ \pi(y,\theta) = \pi(y|\theta)\pi(\theta) = \pi(\theta|y)\pi(y). \] By considering \(\theta'\) and \(\theta''\) the joint distribution is \[ \pi(y,\theta',\theta'') = \pi(y)\pi(\theta'|y)\pi(\theta''|y), \] and it’s easy to see that \(\theta'\) and \(\theta''\) have the same distribution conditionally on \(y\). If we write the joint distribution in an alternative way \[ \pi(y,\theta',\theta'') = \pi(\theta')\pi(y|\theta')\pi(\theta''|y), \] \(\theta'\) and \(\theta''\) still have the same distribution conditionally on \(y\). We can sample from the joint distribution \(\pi(y,\theta',\theta'')\) by first sampling from \(\pi(\theta')\) and \(\pi(y|\theta')\), which is usually easy for generative models. The last step is to sample from the conditional \(\pi(\theta|y)\), which is usually not trivial and instead, for example, a Markov chain Monte Carlo algorithm is used. We can validate the algorithm and its implementation used to sample from \(\pi(\theta''|y)\) by checking that the samples obtained have the same distribution as \(\theta'\) (conditionally on \(y)\).

Cook, Gelman and Rubin (2006) operationalize the approach by drawing \(\theta'_i\) from \(\pi(\theta')\), generating data \(y_i \sim \pi(y_i|\theta'_i)\) and then using the algorithm to be validated to draw a sample \(\theta''_1,\ldots,\theta''_S \sim \pi(\theta''|y_i)\). If the algorithm and its implementation are correct, then \(\theta'_i,\theta''_1,\ldots,\theta''_S\) conditional on \(y_i\) are draws from the same distribution. Cook, Gelman and Rubin (2006) propose to compute empirical PIT valued for \(\theta'_i\) that they show to be uniformly distributed given \(S \to \infty\). The process is repeated for \(i=1,\ldots,N\) and \(N\) empirical PIT values are used for testing. Cook, Gelman and Rubin (2006) propose to use \(\chi^2\)-test for the inverse of the normal CDF of the empirical PIT values. However, with finite \(S\) this approach doesn’t correctly take into account the discreteness or the effect of correlated sample from Markov chain Gelman (2017).

By thinning \(\theta_1^{''},\ldots,\theta_S^{''}\) to be approximately independent, the uniformity of empirical PIT values can be tested with the approach presented in Säilynoja+Buerkner+Vehtari:2020.

Simulation based calibration conditional on observed data

When using weakly informative priors, most of the prior mass can be in the region of the parameter space where the inference works well, but a small amount of prior mass can also be in the regions where inference is likely to fail. We could update the prior to avoid such regions, but if the posterior given observed data is concentrated far from the problematic regions we could instead focus on assessing whether the inference works around the posterior.

Considering that given the sequential update rule in Bayesian approach, an old posterior can be a new prior and we can naturally consider SBC conditional on the observed data \(y_{\mathrm{obs}}\). Thus, we operationalize the approach by drawing \(\theta'_i\) from \(\pi(\theta' | y_{\mathrm{obs}})\), generating new data \(y_i \sim \pi(y_i|\theta'_i)\) and then using the algorithm to be validated to draw a sample \(\theta''_1,\ldots,\theta''_S \sim \pi(\theta'' | y_i, y_{\mathrm{obs}})\). If the algorithm and its implementation are correct, then \(\theta'_i,\theta''_1,\ldots,\theta''_S\) conditional on \(y_i\) and \(y_{\mathrm{obs}}\) are draws from the same distribution.

  • In prior SBC, the prior formulated so that it is easy to draw exactly from the prior (and we assume no mistakes are made when generating draws from the prior), and exact prior draws are compared to draws obtained by the approximate inference algorithm (the approach can also detect mistakes in the model code used in the inference).
  • If we would be able to get exact draws from the posterior, we could directly compare these exact draws to any approximate inference result, and posterior SBC is not needed.
  • In posterior SBC, we are comparing the same algorithm drawing from the original posterior and the updated posterior. If the algorithm is not consistent when observing more data, SBC may be able to detect this (with finite number of SBC iterations and finite sample sizes, we may miss small discrepancies).
  • It is possible that inference could work given the observed data, but not anymore with additional data. The differences in the shape of the posterior given the observed data and the new posteriors in posterior SBC are likely to be smaller than the differences in the shape of different posteriors in the prior SBC approach.

normal(mu, 1) model

We start by illustrating the idea of prior SBC and posterior SBC using a simple \(\mathrm{normal}(\mu, 1)\) model. Given prior draws of \(\mu\), we generate data sets with \(10\) observations.

Illustration of prior SBC

Prior parameters

mu0=0
tau0=10

Plot the prior

p0 = ggplot(data = data.frame(x = c(-40, 40)), aes(x)) +
  stat_function(fun = dnorm, n = 101, args = list(mean = mu0, sd = tau0), linetype='dashed') +
  theme(axis.text.y = element_blank(),
        axis.line.y=element_blank(),
        axis.ticks.y=element_blank())+
  ylab('') 
p0

Observation model scale

sigma=1

Number of observations

N=10

Run simulations

pp = p0
for (i in 1:10) {
  set.seed(1000+i)
  # draw from the prior
  mug=rnorm(1, mean=mu0, sd=tau0)
  # generate data from the predictive distribution given the parameter value sampled from the prior
  yg=rnorm(N, mean=mug, sd=sigma)
  # posterior
  ybar=mean(yg)
  mup=(mu0/tau0^2+N*ybar/sigma^2)/(1/tau0^2+N/sigma^2)
  taup=sqrt(1/(1/tau0^2+N/sigma^2))
  # draw from the posterior
  mupg=rnorm(1, mean=mup, sd=taup)
  # add prior draw, posterior, and posterior draw to the plot
  pp = pp +
    stat_function(fun = function(...) dnorm(...)/33, n = 1001, args = list(mean = mup, sd = taup), alpha=0.3) +
    annotate(geom = "point", x=mug, y=0, color='red', alpha=0.9)+
    annotate(geom = "point", x=mupg, y=0, color='blue', alpha=0.9)
}
pp

The typical feature of prior SBC is visible, that is, the conditional posteriors are much more narrow than the prior distribution. We illustrate later how this affects how the prior and conditional posterior draws should be compared.

Illustration of posterior SBC

We assume we have observed 10 observations with mean \(8.6\). Given posterior draws of \(\mu\) given \(y_\mathrm{obs}\), we generate additional data sets with \(10\) observations each. In posterior SBC, we run the inference given original \(y_\mathrm{obs}\) and new additional data.

Prior

mu0=0
tau0=10

Observation model scale

sigma=1

Number of observations

N=10

Observed data mean

ybar=8.6

Posterior given the observed data

mup=(mu0/tau0^2+N*ybar/sigma^2)/(1/tau0^2+N/sigma^2)
taup=sqrt(1/(1/tau0^2+N/sigma^2))

Plot the posterior

pp1 = ggplot(data = data.frame(x = c(7.4, 9.7)), aes(x)) +
  stat_function(fun = dnorm, n = 101, args = list(mean = mup, sd = taup), linetype='dashed') +
  theme(axis.text.y = element_blank(),
        axis.line.y=element_blank(),
        axis.ticks.y=element_blank())+
  ylab('') 
pp1

Run simulations

pp2 = pp1
for (i in 1:10) {
  set.seed(1000+i)
  # draw from the posterior
  mug2=rnorm(1, mean=mup, sd=taup)
  # generate data from the predictive distribution given the parameter value sampled from the posterior
  yg2=rnorm(N, mean=mug2, sd=sigma)
  # second posterior
  ybar2=mean(yg2)
  mup2=(mup/taup^2+N*ybar2/sigma^2)/(1/taup^2+N/sigma^2)
  taup2=sqrt(1/(1/taup^2+N/sigma^2))
  # draw from the second posterior
  mupg2=rnorm(1, mean=mup2, sd=taup2)
  # add posterior draw, second posterior, and draw from the second posterior to the plot
  pp2 = pp2 +
    stat_function(fun = function(...) dnorm(...)/2, n = 1001, args = list(mean = mup2, sd = taup2), alpha=0.3) +
    annotate(geom = "point", x=mug2, y=0, color='red', alpha=0.9)+
    annotate(geom = "point", x=mupg2, y=0, color='blue', alpha=0.9)
}
pp2

We see the typical feature of posterior SBC, that is, the conditional posteriors are only slightly more narrow than the original posterior distribution (factor of $). We illustrate later how this affects how the posterior and conditional posterior draws should be compared.

Prior SBC

We now illustrate the behavior of prior SBC given a correct and incorrect conditional posterior inference.

Correct posterior

mugs = mups = pits = numeric()
pp = p0
for (i in 1:1000) {
  set.seed(1000+i)
  mug=rnorm(1, mean=mu0, sd=tau0)
  mugs[i]=mug[1]
  yg=rnorm(N, mean=mug, sd=sigma)
  ybar=mean(yg)
  mup=(mu0/tau0^2+N*ybar/sigma^2)/(1/tau0^2+N/sigma^2)
  taup=sqrt(1/(1/tau0^2+N/sigma^2))
  mupg=rnorm(1000, mean=mup, sd=taup)
  mups[i]=mupg[1]
  pits[i]=mean(mups<mug)
}
df=data.frame(mugs,mups,pits)

p2=ggplot(data=df,aes(x=mugs,y=mups))+
  geom_point(alpha=0.5,color='blue')+
  geom_abline()+
  labs(x=TeX('$\\mu\' \\sim p(\\mu)$'),y=TeX('$\\mu\'\' \\sim p(\\mu | y_i)$'))
plims = range(c(ggplot_build(p2)$layout$panel_params[[1]]$x.range,
                 ggplot_build(p2)$layout$panel_params[[1]]$y.range))
p2+lims(x=plims,y=plims)

Prior draws and conditional posterior draws are highly correlated.

ggplot(data=df,aes(x=sort(mugs),y=sort(mups)))+
  geom_point(alpha=.3,color='blue')+
  geom_abline()+
  labs(x=TeX('sorted $\\mu\' \\sim p(\\mu)$'),y=TeX('sorted $\\mu\'\' \\sim p(\\mu | y_i)$'))

QQ-plot also looks good.

ggplot(data=df,aes(x=seq(0,1,length.out=1000),y=sort(pits)))+
  geom_line(color='blue',size=2)+
  geom_abline()+
  labs(x='Uniform',y='PIT')

ECDF of probability integral transformation (PIT) looks also good as it should.

Incorrect posterior

Here we have incorrect inference, so that posterior scale formula is missing the square root (a mistake we actually first made).

mugs = mups = pits = numeric()
pp = p0
for (i in 1:1000) {
  set.seed(1000+i)
  mug=rnorm(1, mean=mu0, sd=tau0)
  mugs[i]=mug[1]
  yg=rnorm(N, mean=mug, sd=sigma)
  ybar=mean(yg)
  mup=(mu0/tau0^2+N*ybar/sigma^2)/(1/tau0^2+N/sigma^2)
  # correct
  # taup=sqrt(1/(1/tau0^2+N/sigma^2))
  # wrong
  taup=(1/(1/tau0^2+N/sigma^2))
  mupg=rnorm(1000, mean=mup, sd=taup)
  mups[i]=mupg[1]
  pits[i]=mean(mupg<mug)
}
df=data.frame(mugs,mups,pits)

p2=ggplot(data=df,aes(x=mugs,y=mups))+
  geom_point(alpha=0.5,color='blue')+
  geom_abline()+
  labs(x=TeX('$\\mu\' \\sim p(\\mu)$'),y=TeX('$\\mu\'\' \\sim p(\\mu | y_i)$'))
plims = range(c(ggplot_build(p2)$layout$panel_params[[1]]$x.range,
                 ggplot_build(p2)$layout$panel_params[[1]]$y.range))
p2+lims(x=plims,y=plims)

As the conditional posteriors are very narrow, the draws from the conditional posteriors are highly correlated with the prior draws and we can’t see anything being wrong.

ggplot(data=df,aes(x=sort(mugs),y=sort(mups)))+
  geom_point(alpha=.3,color='blue')+
  geom_abline()+
  labs(x=TeX('sorted $\\mu\' \\sim p(\\mu)$'),y=TeX('sorted $\\mu\'\' \\sim p(\\mu | y_i)$'))

QQ-plot also looks good.

ggplot(data=df,aes(x=seq(0,1,length.out=1000),y=sort(pits)))+
  geom_line(color='blue',size=2)+
  geom_abline()+
  labs(x='Uniform',y='PIT')

PIT plot looks terrible. The conditional posteriors are too narrow, and thus PIT values are not uniformly distributed.

Posterior SBC

We now illustrate the behavior of posterior SBC given a correct and incorrect conditional posterior inference.

Correct posterior

Observed data mean

ybar=8.6

Posterior given the observed data

mup=(mu0/tau0^2+N*ybar/sigma^2)/(1/tau0^2+N/sigma^2)
taup=sqrt(1/(1/tau0^2+N/sigma^2))

Run simulations

mug2s = mup2s = pit2s = numeric()
pp2 = pp1
for (i in 1:1000) {
  set.seed(1000+i)
  # draw from the posterior
  mug2=rnorm(1, mean=mup, sd=taup)
  mug2s[i]=mug2
  # generate data from the predictive distribution given the parameter value sampled from the posterior
  yg2=rnorm(N, mean=mug2, sd=sigma)
  # second posterior
  ybar2=mean(yg2)
  mup2=(mup/taup^2+N*ybar2/sigma^2)/(1/taup^2+N/sigma^2)
  taup2=sqrt(1/(1/taup^2+N/sigma^2))
  # draw from the second posterior
  mupg2=rnorm(1000, mean=mup2, sd=taup2)
  mup2s[i]=mupg2[1]
  pit2s[i]=mean(mupg2<mug2)
}
df=data.frame(mug2s,mup2s,pit2s)

p2=ggplot(data=df,aes(x=mug2s,y=mup2s))+
  geom_point(alpha=0.5,color='blue')+
  geom_abline()+
  labs(x=TeX('$\\mu\' \\sim p(\\mu | y_{\\mathrm{obs}})$'),y=TeX('$\\mu\'\' \\sim p(\\mu | y_i, y_{\\mathrm{obs}})$'))
plims = range(c(ggplot_build(p2)$layout$panel_params[[1]]$x.range,
                 ggplot_build(p2)$layout$panel_params[[1]]$y.range))
p2+lims(x=plims,y=plims)

Posterior draws and conditional posterior draws are weakly correlated.

ggplot(data=df,aes(x=sort(mug2s),y=sort(mup2s)))+
  geom_point(alpha=.3,color='blue')+
  geom_abline()+
  labs(x=TeX('sorted $\\mu\' \\sim p(\\mu | y_{\\mathrm{obs}})$'),y=TeX('sorted $\\mu\'\' \\sim p(\\mu | y_i, y_{\\mathrm{obs}})$'))

QQ-plot also looks good.

ggplot(data=df,aes(x=seq(0,1,length.out=1000),y=sort(pit2s)))+
  geom_line(color='blue',size=2)+
  geom_abline()+
  labs(x='Uniform',y='PIT')

ECDF of probability integral transformation (PIT) looks also good as it should.

Incorrect posterior 1

Here we have incorrect inference, so that posterior scale formula is missing the square root.

Observed data mean

ybar=8.6

Posterior given the observed data

mup=(mu0/tau0^2+N*ybar/sigma^2)/(1/tau0^2+N/sigma^2)
taup=(1/(1/tau0^2+N/sigma^2))

Run simulations

mug2s = mup2s = pit2s = numeric()
pp2 = pp1
for (i in 1:1000) {
  set.seed(1000+i)
  # draw from the posterior
  mug2=rnorm(1, mean=mup, sd=taup)
  mug2s[i]=mug2
  # generate data from the predictive distribution given the parameter value sampled from the posterior
  yg2=rnorm(N, mean=mug2, sd=sigma)
  # second posterior
  ybar2=mean(yg2)
  mup2=(mup/taup^2+N*ybar2/sigma^2)/(1/taup^2+N/sigma^2)
  taup2=(1/(1/taup^2+N/sigma^2))
  # draw from the second posterior
  mupg2=rnorm(1000, mean=mup2, sd=taup2)
  mup2s[i]=mupg2[1]
  pit2s[i]=mean(mupg2<mug2)
}
df=data.frame(mug2s,mup2s,pit2s)

p2 = ggplot(data=df,aes(x=mug2s,y=mup2s))+
  geom_point(alpha=0.5,color='blue')+
  geom_abline()+
  labs(x=TeX('$\\mu\' \\sim p(\\mu | y_{\\mathrm{obs}})$'),y=TeX('$\\mu\'\' \\sim p(\\mu | y_i, y_{\\mathrm{obs}})$'))
plims <- range(c(ggplot_build(p2)$layout$panel_params[[1]]$x.range,
                 ggplot_build(p2)$layout$panel_params[[1]]$y.range))
p2+lims(x=plims,y=plims)

Posterior draws and conditional posterior draws are weakly correlated, but the conditional posterior draws have much smaller variability.

ggplot(data=df,aes(x=sort(mug2s),y=sort(mup2s)))+
  geom_point(alpha=.3,color='blue')+
  geom_abline()+
  labs(x=TeX('sorted $\\mu\' \\sim p(\\mu | y_{\\mathrm{obs}})$'),y=TeX('sorted $\\mu\'\' \\sim p(\\mu | y_i, y_{\\mathrm{obs}})$'))

QQ-plot also shows that the conditional posterior draws have much smaller variability.

ggplot(data=df,aes(x=seq(0,1,length.out=1000),y=sort(pit2s)))+
  geom_line(color='blue',size=2)+
  geom_abline()+
  labs(x='Uniform',y='PIT')

PIT plot looks also terrible. The conditional posteriors are too narrow, and thus PIT values are not uniformly distributed.

Incorrect posterior 2

Here we’re again underestimating the posterior variance, but less than in the first incorrect inference example. Now we compute the variance as 80% from the true posterior variance.

Observed data mean

ybar=8.6

Posterior given the observed data

mup=(mu0/tau0^2+N*ybar/sigma^2)/(1/tau0^2+N/sigma^2)
taup=0.8*sqrt(1/(1/tau0^2+N/sigma^2))

Run simulations

mug2s = mup2s = pit2s = numeric()
pp2 = pp1
for (i in 1:1000) {
  set.seed(1000+i)
  # draw from the posterior
  mug2=rnorm(1, mean=mup, sd=taup)
  mug2s[i]=mug2
  # generate data from the predictive distribution given the parameter value sampled from the posterior
  yg2=rnorm(N, mean=mug2, sd=sigma)
  # second posterior
  ybar2=mean(yg2)
  mup2=(mup/taup^2+N*ybar2/sigma^2)/(1/taup^2+N/sigma^2)
  taup2=0.8*sqrt(1/(1/taup^2+N/sigma^2))
  # draw from the second posterior
  mupg2=rnorm(1000, mean=mup2, sd=taup2)
  mup2s[i]=mupg2[1]
  pit2s[i]=mean(mupg2<mug2)
}
df=data.frame(mug2s,mup2s,pit2s)

p2=ggplot(data=df,aes(x=mug2s,y=mup2s))+
  geom_point(alpha=0.5,color='blue')+
  geom_abline()+
  labs(x=TeX('$\\mu\' \\sim p(\\mu | y_{\\mathrm{obs}})$'),y=TeX('$\\mu\'\' \\sim p(\\mu | y_i, y_{\\mathrm{obs}})$'))
plims <- range(c(ggplot_build(p2)$layout$panel_params[[1]]$x.range,
                 ggplot_build(p2)$layout$panel_params[[1]]$y.range))
p2+lims(x=plims,y=plims)

Posterior draws and conditional posterior draws are weakly correlated. It is difficult to see any discrepancy from this plot.

ggplot(data=df,aes(x=sort(mug2s),y=sort(mup2s)))+
  geom_point(alpha=.3,color='blue')+
  geom_abline()+
  labs(x=TeX('sorted $\\mu\' \\sim p(\\mu | y_{\\mathrm{obs}})$'),y=TeX('sorted $\\mu\'\' \\sim p(\\mu | y_i, y_{\\mathrm{obs}})$'))

QQ-plot indicates problems at tails. The conditional posterior seems to be slightly too narrow.

ggplot(data=df,aes(x=seq(0,1,length.out=1000),y=sort(pit2s)))+
  geom_line(color='blue',size=2)+
  geom_abline()+
  labs(x='Uniform',y='PIT')

PIT plot confirms the suspicious. The conditional posteriors are too narrow, and thus PIT values are not uniformly distributed.

8-schools

Next we illustrate the posterior SBC in case of a hierarchical model where a certain parameterization can lead to a funnel shaped posterior that is difficult to sample with fixed step size (dynamic) Hamiltonian Monte Carlo.

8-schools data

dat = list(J=8, y=c(28,8,-3,7,-1,1,18,12), sigma=c(15,10,16,11,9,11,10,18))

Non-centered parameterization - dynamic HMC

For 8-schools data and model, it is known that non-centered parameterization produces a posterior that is relatively easy to sample with fixed step size dynamic HMC. We expect that posterior SBC doesn’t detect any problems.

8-schools model with non-centered parameterization

mod_ncp = cmdstan_model(stan_file = 'schools_ncp.stan')

sample from the posterior given the observed data

out = capture.output(
  fit_ncp <- mod_ncp$sample(data=dat, refresh=0, show_messages=FALSE, seed=0))
draws_ncp = as_draws_rvars(thin_draws(fit_ncp$draws(),20))
tau_ncp = as_draws_matrix(subset_draws(draws_ncp, variable="tau"))

draws from the posterior predictive distribution

yrep_ncp = as_draws_matrix(subset_draws(draws_ncp, variable="yrep"))

200 iterations of posterior SBC

pitp_ncp = taup_ncp = numeric()
for (j in 1:200) {
  # combine the original data with posterior predictive data
  datp = list(J = 2*dat$J,
              y = c(dat$y, yrep_ncp[j,]),
              sigma = rep(dat$sigma, 2))
  # sample from the second posterior
  out = capture.output(
    fitp <- mod_ncp$sample(data=datp, refresh=0, show_messages = FALSE, seed=j))
  drawsp = as_draws_rvars(fitp$draws())
  # one draw from the second posterior
  taup_ncp[j] = as_draws_matrix(drawsp$tau)[1]
  # PIT value
  pitp_ncp[j] = mean(drawsp$tau < as.vector(tau_ncp[j]))
}

df=data.frame(tau_ncp,taup_ncp,pitp_ncp)

ggplot(data=df,aes(x=tau_ncp,y=taup_ncp))+geom_point(alpha=0.5,color='blue')+
  geom_abline()+
  scale_x_log10()+scale_y_log10()+
  labs(x=TeX('$\\tau\' \\sim p(\\tau | y_{\\mathrm{obs}})$'),y=TeX('$\\tau\'\' \\sim p(\\tau | y_i, y_{\\mathrm{obs}})$'))

Posterior draws and conditional posterior draws are weakly correlated.

ggplot(data=df,aes(x=sort(tau_ncp),y=sort(taup_ncp)))+
  geom_point(alpha=.3,color='blue')+
  geom_abline()+
  scale_x_log10()+scale_y_log10()+
  labs(x=TeX('sorted $\\tau\' \\sim p(\\tau | y_{\\mathrm{obs}})$'),y=TeX('sorted $\\tau\'\' \\sim p(\\tau | y_i, y_{\\mathrm{obs}})$'))

QQ-plot looks good.

ggplot(data=df,aes(x=seq(0,1,length.out=200),y=sort(pitp_ncp)))+
  geom_line(color='blue',size=2)+
  geom_abline()+
  labs(x='Uniform',y='PIT')

ECDF of probability integral transformation (PIT) looks also good as we expected.

Centered parameterization - dynamic HMC

For 8-schools data and model, it is known that centered parameterization produces a posterior that has strong funnel shape and with fixed step size (dynamic) HMC is unable to explore the narrow part of the funnel. The HMC specific and generic MCMC diagnostics indicate these problems, and thus posterior SBC is not necessary here, but as a well known example 8-schools centered parameterization works as a useful illustration.

8-schools model with centered parameterization model

mod_cp = cmdstan_model(stan_file = 'schools_cp.stan')

sample from the posterior given the observed data

out = capture.output(
  fit_cp <- mod_cp$sample(data=dat, refresh=0, show_messages=FALSE, seed=0))
draws_cp = as_draws_rvars(thin_draws(fit_cp$draws(),20))
tau_cp = as_draws_matrix(subset_draws(draws_cp, variable="tau"))

draws from the posterior predictive distribution

yrep_cp = as_draws_matrix(subset_draws(draws_cp, variable="yrep"))

200 iterations of posterior SBC

pitp_cp = taup_cp = numeric()
for (j in 1:200) {
  # combine the original data with posterior predictive data
  datp = list(J = 2*dat$J,
              y = c(dat$y, yrep_cp[j,]),
              sigma = rep(dat$sigma, 2))
  # sample from the second posterior
  out = capture.output(
    fitp <- mod_cp$sample(data=datp, refresh=0, show_messages = FALSE, seed=j))
  drawsp = as_draws_rvars(fitp$draws())
  # one draw from the second posterior
  taup_cp[j] = as_draws_matrix(drawsp$tau)[1]
  # PIT value
  pitp_cp[j] = mean(drawsp$tau < as.vector(tau_cp[j]))
}

df=data.frame(tau_cp,taup_cp,pitp_cp)

p2=ggplot(data=df,aes(x=tau_cp,y=taup_cp))+
  geom_point(alpha=0.5,color='blue')+
  geom_abline()+
  scale_x_log10()+
  scale_y_log10()+
  labs(x=TeX('$\\tau\' \\sim p(\\tau | y_{\\mathrm{obs}})$'),y=TeX('$\\tau\'\' \\sim p(\\tau | y_i, y_{\\mathrm{obs}})$'))
plims = range(c(ggplot_build(p2)$layout$panel_params[[1]]$x.range,
                 ggplot_build(p2)$layout$panel_params[[1]]$y.range))
p2+scale_x_log10(limits=10^plims)+
  scale_y_log10(limits=10^plims)

Posterior draws and conditional posterior draws are weakly correlated. It is difficult to see any discrepancy in this plot.

ggplot(data=df,aes(x=sort(tau_cp),y=sort(taup_cp)))+
  geom_point(alpha=.3,color='blue')+
  geom_abline()+
  scale_x_log10()+
  scale_y_log10()+
  labs(x=TeX('sorted $\\tau\' \\sim p(\\tau | y_{\\mathrm{obs}})$'),y=TeX('sorted $\\tau\'\' \\sim p(\\tau | y_i, y_{\\mathrm{obs}})$'))

QQ-plot reveals clear discrepancy in small values of \(\tau\). Here we do get sometimes much smaller conditional posterior draws than the smallest original posterior draws, which indicates that the inference for the original posterior is failing.

ggplot(data=df,aes(x=seq(0,1,length.out=200),y=sort(pitp_cp)))+
  geom_line(color='blue',size=2)+
  geom_abline()+
  labs(x='Uniform',y='PIT')

PIT plot doesn’t show the discrepancy that clearly, although there is some suspicion in the small values.

Non-centered parameterization - ADVI

Automatic differentiation variational inference uses normal approximation. Yao et al. (2018) demonstrate that (given enough computation time) it works reasonably for the non-centered parameterization.

8-schools model with non-centered parameterization

mod_ncp = cmdstan_model(stan_file = 'schools_ncp.stan')

sample from the posterior given the observed data

out = capture.output(
  fit_ncpv <- mod_ncp$variational(data=dat, refresh=0, seed=0, tol_rel_obj=1e-4, iter=1e5))
draws_ncpv = as_draws_rvars(thin_draws(fit_ncpv$draws(),5))
tau_ncpv = as_draws_matrix(subset_draws(draws_ncpv, variable="tau"))

draws from the posterior predictive distribution

yrep_ncpv = as_draws_matrix(subset_draws(draws_ncpv, variable="yrep"))

200 iterations of posterior SBC

pitp_ncpv = taup_ncpv = numeric()
for (j in 1:200) {
  # combine the original data with posterior predictive data
  datp = list(J = 2*dat$J,
              y = c(dat$y, yrep_ncpv[j,]),
              sigma = rep(dat$sigma, 2))
  # sample from the second posterior
  out = capture.output(
    fitp <- mod_ncp$variational(data=datp, refresh=0, seed=j, tol_rel_obj=1e-4, iter=1e5))
  drawsp = as_draws_rvars(fitp$draws())
  # one draw from the second posterior
  taup_ncpv[j] = as_draws_matrix(drawsp$tau)[1]
  # PIT value
  pitp_ncpv[j] = mean(drawsp$tau < as.vector(tau_ncpv[j]))
}

df=data.frame(tau_ncpv,taup_ncpv,pitp_ncpv)

p2=ggplot(data=df,aes(x=tau_ncpv,y=taup_ncpv))+
  geom_point(alpha=0.5,color='blue')+
  geom_abline()+
  scale_x_log10()+
  scale_y_log10()+
  labs(x=TeX('$\\tau\' \\sim p(\\tau | y_{\\mathrm{obs}})$'),y=TeX('$\\tau\'\' \\sim p(\\tau | y_i, y_{\\mathrm{obs}})$'))
plims = range(c(ggplot_build(p2)$layout$panel_params[[1]]$x.range,
                 ggplot_build(p2)$layout$panel_params[[1]]$y.range))
p2+scale_x_log10(limits=10^plims)+
  scale_y_log10(limits=10^plims)

Posterior draws and conditional posterior draws are weakly correlated. It is difficult to see any discrepancy in this plot.

ggplot(data=df,aes(x=sort(tau_ncpv),y=sort(taup_ncpv)))+
  geom_point(alpha=.3,color='blue')+
  geom_abline()+
  scale_x_log10()+
  scale_y_log10()+
  labs(x=TeX('sorted $\\tau\' \\sim p(\\tau | y_{\\mathrm{obs}})$'),y=TeX('sorted $\\tau\'\' \\sim p(\\tau | y_i, y_{\\mathrm{obs}})$'))

QQ-plot indicates that the original posterior is likely to be narrower than the true posterior.

ggplot(data=df,aes(x=seq(0,1,length.out=200),y=sort(pitp_ncpv)))+
  geom_line(color='blue',size=2)+
  geom_abline()+
  labs(x='Uniform',y='PIT')

PIT plot indicates problems in the extreme left tail.

Centered parameterization - ADVI

8-schools model with centered parameterization model

mod_cp = cmdstan_model(stan_file = 'schools_cp.stan')

sample from the posterior given the observed data

out = capture.output(
  fit_cpv <- mod_cp$variational(data=dat, refresh=0, seed=0, tol_rel_obj=1e-4, iter=1e5))
draws_cpv = as_draws_rvars(thin_draws(fit_cpv$draws(),5))
tau_cpv = as_draws_matrix(subset_draws(draws_cpv, variable="tau"))

draws from the posterior predictive distribution

yrep_cpv = as_draws_matrix(subset_draws(draws_cpv, variable="yrep"))

200 iterations of posterior SBC

pitp_cpv = taup_cpv = numeric()
for (j in 1:200) {
  # combine the original data with posterior predictive data
  datp = list(J = 2*dat$J,
              y = c(dat$y, yrep_cpv[j,]),
              sigma = rep(dat$sigma, 2))
  # sample from the second posterior
  out = capture.output(
    fitp <- mod_cp$variational(data=datp, refresh=0, seed=200+j, tol_rel_obj=1e-4, iter=1e5))
  drawsp = as_draws_rvars(fitp$draws())
  # one draw from the second posterior
  taup_cpv[j] = as_draws_matrix(drawsp$tau)[1]
  # PIT value
  pitp_cpv[j] = mean(drawsp$tau < as.vector(tau_cpv[j]))
}

df=data.frame(tau_cpv,taup_cpv,pitp_cpv)

p2=ggplot(data=df,aes(x=tau_cpv,y=taup_cpv))+
  geom_point(alpha=0.5,color='blue')+
  geom_abline()+
  scale_x_log10()+
  scale_y_log10()+
  labs(x=TeX('$\\tau\' \\sim p(\\tau | y_{\\mathrm{obs}})$'),y=TeX('$\\tau\'\' \\sim p(\\tau | y_i, y_{\\mathrm{obs}})$'))
plims = range(c(ggplot_build(p2)$layout$panel_params[[1]]$x.range,
                 ggplot_build(p2)$layout$panel_params[[1]]$y.range))
p2+scale_x_log10(limits=10^plims)+
  scale_y_log10(limits=10^plims)

Posterior draws and conditional posterior draws are weakly correlated. It is difficult to see any discrepancy in this plot.

ggplot(data=df,aes(x=sort(tau_cpv),y=sort(taup_cpv)))+
  geom_point(alpha=.3,color='blue')+
  geom_abline()+
  scale_x_log10()+
  scale_y_log10()+
  labs(x=TeX('sorted $\\tau\' \\sim p(\\tau | y_{\\mathrm{obs}})$'),y=TeX('sorted $\\tau\'\' \\sim p(\\tau | y_i, y_{\\mathrm{obs}})$'))

QQ-plot has some structure, but no clear indication of the problems.

ggplot(data=df,aes(x=seq(0,1,length.out=200),y=sort(pitp_cpv)))+
  geom_line(color='blue',size=2)+
  geom_abline()+
  labs(x='Uniform',y='PIT')

PIT plot shows clearly that the posterior variance is underestimated.

Comparison of approximations

After seeing the diagnostics, we compare all posterior approximations and the conditional posteriors.

rtau=as_draws_df(rvar(cbind(ncp=as.vector(tau_ncp),pncp=taup_ncp,
                            cp=as.vector(tau_cp),pcp=taup_cp,
                            ncpv=as.vector(tau_ncpv),pncpv=taup_ncpv,
                            cpv=as.vector(tau_cpv),pcpv=taup_cpv)))
rtau<-rename_variables(rtau,
                       "Non-centered HMC"='x[ncp]',
                       "Non-centered HMC-SBC"='x[pncp]',
                       "Centered HMC"='x[cp]',
                       "Centered HMC-SBC"='x[pcp]',
                       "Non-centered ADVI"='x[ncpv]',
                       "Non-centered ADVI-SBC"='x[pncpv]',
                       "Centered ADVI"='x[cpv]',
                       "Centered ADVI-SBC"='x[pcpv]')
mcmc_areas(as_draws_matrix(log(rtau)))

We see that

  • non-centered HMC matches non-centered HMC-SBC
  • centered HMC is missing smaller values of tau, which is revealed by centered HMC-SBC
  • non-centered ADVI is close to non-centered HMC-SBC. The ADVI normal approximation has most of the mass where the true posterior (based on non-centered HMC), but the normal approximation is missing the skewness of the true posterior and this was not indicated by the posterior SBC.
  • Centered ADVI looks similar to centered HMC-SBC. The ADVI normal approximation is very different from the true posterior (based on non-centered HMC), and the posterior SBC did indicate severe underestimation of the posterior variance.


References

Cook, S. R., Gelman, A. and Rubin, D. B. (2006) ‘Validation of software for Bayesian models using posterior quantiles’, Journal of Computational and Graphical Statistics, 15(3), pp. 675–692.
Gelman, A. (2017) ‘Correction to Cook, Gelman, and Rubin (2006)’, Journal of Computational and Graphical Statistics, 26(4), pp. 940–940.
Yao, Y., Vehtari, A., Simpson, D. and Gelman, A. (2018) ‘Yes, but did it work?: Evaluating variational inference’, Proceedings of the 35th International Conference on Machine Learning, PMLR 80, pp. 5581–5590.

Licenses

  • Code © 2022, Aki Vehtari, licensed under BSD-3.
  • Text © 2022, Aki Vehtari, licensed under CC-BY-NC 4.0.

Original Computing Environment

sessionInfo()
R version 4.1.2 (2021-11-01)
Platform: x86_64-pc-linux-gnu (64-bit)
Running under: Ubuntu 20.04.3 LTS

Matrix products: default
BLAS/LAPACK: /usr/lib/x86_64-linux-gnu/libmkl_rt.so

locale:
 [1] LC_CTYPE=en_US.UTF-8       LC_NUMERIC=C              
 [3] LC_TIME=fi_FI.UTF-8        LC_COLLATE=en_US.UTF-8    
 [5] LC_MONETARY=fi_FI.UTF-8    LC_MESSAGES=en_US.UTF-8   
 [7] LC_PAPER=fi_FI.UTF-8       LC_NAME=C                 
 [9] LC_ADDRESS=C               LC_TELEPHONE=C            
[11] LC_MEASUREMENT=fi_FI.UTF-8 LC_IDENTIFICATION=C       

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] bayesplot_1.8.1      ggplot2_3.3.5        latex2exp_0.5.0     
[4] dplyr_1.0.7          posterior_1.1.0.9000 cmdstanr_0.4.0.9000 

loaded via a namespace (and not attached):
 [1] tidyselect_1.1.1     xfun_0.28            bslib_0.3.1         
 [4] reshape2_1.4.4       purrr_0.3.4          colorspace_2.0-2    
 [7] vctrs_0.3.8          generics_0.1.1       htmltools_0.5.2     
[10] yaml_2.2.1           utf8_1.2.2           rlang_0.4.12        
[13] jquerylib_0.1.4      pillar_1.6.4         glue_1.5.1          
[16] withr_2.4.2          DBI_1.1.1            distributional_0.2.2
[19] matrixStats_0.61.0   lifecycle_1.0.1      plyr_1.8.6          
[22] stringr_1.4.0        munsell_0.5.0        gtable_0.3.0        
[25] evaluate_0.14        labeling_0.4.2       knitr_1.36          
[28] fastmap_1.1.0        ps_1.6.0             fansi_0.5.0         
[31] highr_0.9            Rcpp_1.0.7           scales_1.1.1        
[34] backports_1.4.0      checkmate_2.0.0      jsonlite_1.7.2      
[37] abind_1.4-5          farver_2.1.0         tensorA_0.36.2      
[40] digest_0.6.28        stringi_1.7.6        processx_3.5.2      
[43] grid_4.1.2           tools_4.1.2          magrittr_2.0.1      
[46] sass_0.4.0           tibble_3.1.6         crayon_1.4.2        
[49] pkgconfig_2.0.3      ellipsis_0.3.2       data.table_1.14.2   
[52] ggridges_0.5.3       assertthat_0.2.1     rmarkdown_2.11      
[55] R6_2.5.1             compiler_4.1.2      


IycgLS0tCiMnIHRpdGxlOiAiU2ltdWxhdGlvbiBCYXNlZCBDYWxpYnJhdGlvbiBDb25kaXRpb25hbCBvbiBPYnNlcnZlZCBEYXRhIgojJyBhdXRob3I6ICJBa2kgVmVodGFyaSIKIycgZGF0ZTogIkZpcnN0IHZlcnNpb24gMjAyMi0wMS0wMy4gTGFzdCBtb2RpZmllZCBgciBmb3JtYXQoU3lzLkRhdGUoKSlgLiIKIycgb3V0cHV0OgojJyAgIGh0bWxfZG9jdW1lbnQ6CiMnICAgICB0aGVtZTogcmVhZGFibGUKIycgICAgIHRvYzogdHJ1ZQojJyAgICAgdG9jX2RlcHRoOiAzCiMnICAgICB0b2NfZmxvYXQ6IHRydWUKIycgICAgIGNvZGVfZG93bmxvYWQ6IHRydWUKIycgYmlibGlvZ3JhcGh5OiBwb3N0c2JjLmJpYgojJyBjc2w6IGhhcnZhcmQtY2l0ZS10aGVtLXJpZ2h0LmNzbAojJyAtLS0KIycKIycgIyBJbnRyb2R1Y3Rpb24KIycKIycgU2ltdWxhdGlvbiBiYXNlZCBjYWxpYnJhdGlvbiAoU0JDKSBjYW4gYmUgdXNlZCB0byB2YWxpZGF0ZQojJyBpbmZlcmVuY2UgYWxnb3JpdGhtcyBieSByZXBlYXRlZCBpbmZlcmVuY2UgZ2l2ZW4gcmVwZWF0ZWQgc2ltdWxhdGVkCiMnIGRhdGEgZnJvbSBhIGdlbmVyYXRpdmUgbW9kZWwuIFRoZSBvcmlnaW5hbCBhbmQgY29tbW9ubHkgdXNlZAojJyBhcHByb2FjaCBnZW5lcmF0ZWQgdGhlIGdlbmVyYXRpdmUgbW9kZWwgcGFyYW1ldGVycyBmcm9tIHByaW9yLCBhbmQKIycgdGh1cyB0aGUgYXBwcm9hY2ggaXMgdGVzdGluZyB3aGV0aGVyIGluZmVyZW5jZSB3b3JrcyBmb3Igc2ltdWxhdGVkCiMnIGRhdGEgZ2VuZXJhdGVkIHdpdGggcGFyYW1ldGVyIHZhbHVlcyBwbGF1c2libGUgdW5kZXIgdGhhdAojJyBwcmlvci4gVGhpcyBpcyBuYXR1cmFsIGFuZCBkZXNpcmFibGUgd2hlbiB3ZSB3YW50IHRvIHRlc3Qgd2hldGhlcgojJyB0aGUgaW5mZXJlbmNlIHdvcmtzIGZvciBmb3IgbWFueSBkaWZmZXJlbnQgdHlwZXMgb2YgZGF0YSBzZXRzIHdlCiMnIG1pZ2h0IG9ic2VydmUuIEFmdGVyIG9ic2VydmluZyBkYXRhLCB3ZSBhcmUgaW50ZXJlc3RlZCB3aGV0aGVyIHRoZQojJyBpbmZlcmVuY2UgZGlkIHdvcmsgY29uZGl0aW9uYWwgb24gdGhhdCBkYXRhLCBhbmQgdGhlIHBvc3RlcmlvcgojJyBnaXZlbiB0aGUgb2JzZXJ2ZWQgZGF0YSBpcyBvZnRlbiBtdWNoIG1vcmUgY29uY2VudHJhdGVkIHRoYW4gdGhlCiMnIHByaW9yLiBIZXJlIHdlIGRlbW9uc3RyYXRlIGhvdyBTQkMgY2FuIGJlIHVzZWQgY29uZGl0aW9uYWxseSBvbgojJyBvYnNlcnZlZCBkYXRhLgojJyAKIycgIyMgU2ltdWxhdGlvbiBiYXNlZCBjYWxpYnJhdGlvbgojJyAKIycgQENvb2srR2VsbWFuK1J1YmluOjIwMDYgcHJvcG9zZWQgYSBzaW11bGF0aW9uLWJhc2VkIGNhbGlicmF0aW9uCiMnIG1ldGhvZCBmb3IgdmFsaWRhdGluZyBCYXllc2lhbiBpbmZlcmVuY2Ugc29mdHdhcmUuIFRoZSBpZGVhIGlzCiMnIGJhc2VkIG9uIHRoZSBmYWN0IHdlIGNhbiBmYWN0b3IgdGhlIGpvaW50IGRpc3RyaWJ1dGlvbiBvZiBkYXRhCiMnICR5JCBhbmQgcGFyYW1ldGVycyAkXHRoZXRhJCBpbiB0d28gd2F5cwojJyAkJAojJyAgIFxwaSh5LFx0aGV0YSkgPSBccGkoeXxcdGhldGEpXHBpKFx0aGV0YSkgPSBccGkoXHRoZXRhfHkpXHBpKHkpLgojJyAkJAojJyBCeSBjb25zaWRlcmluZyAkXHRoZXRhJyQgYW5kICRcdGhldGEnJyQgdGhlIGpvaW50IGRpc3RyaWJ1dGlvbiBpcyAKIycgJCQKIycgICBccGkoeSxcdGhldGEnLFx0aGV0YScnKSA9IFxwaSh5KVxwaShcdGhldGEnfHkpXHBpKFx0aGV0YScnfHkpLAojJyAkJAojJyBhbmQgaXQncyBlYXN5IHRvIHNlZSB0aGF0ICRcdGhldGEnJCBhbmQgJFx0aGV0YScnJCBoYXZlIHRoZSBzYW1lCiMnIGRpc3RyaWJ1dGlvbiBjb25kaXRpb25hbGx5IG9uICR5JC4gSWYgd2Ugd3JpdGUgdGhlIGpvaW50CiMnIGRpc3RyaWJ1dGlvbiBpbiBhbiBhbHRlcm5hdGl2ZSB3YXkKIycgJCQKIycgICBccGkoeSxcdGhldGEnLFx0aGV0YScnKSA9IFxwaShcdGhldGEnKVxwaSh5fFx0aGV0YScpXHBpKFx0aGV0YScnfHkpLAojJyAkJAojJyAkXHRoZXRhJyQgYW5kICRcdGhldGEnJyQgc3RpbGwgaGF2ZSB0aGUgc2FtZSBkaXN0cmlidXRpb24KIycgY29uZGl0aW9uYWxseSBvbiAkeSQuIFdlIGNhbiBzYW1wbGUgZnJvbSB0aGUgam9pbnQgZGlzdHJpYnV0aW9uCiMnICRccGkoeSxcdGhldGEnLFx0aGV0YScnKSQgYnkgZmlyc3Qgc2FtcGxpbmcgZnJvbSAkXHBpKFx0aGV0YScpJCBhbmQKIycgJFxwaSh5fFx0aGV0YScpJCwgd2hpY2ggaXMgdXN1YWxseSBlYXN5IGZvciBnZW5lcmF0aXZlIG1vZGVscy4gVGhlCiMnIGxhc3Qgc3RlcCBpcyB0byBzYW1wbGUgZnJvbSB0aGUgY29uZGl0aW9uYWwgJFxwaShcdGhldGF8eSkkLCB3aGljaAojJyBpcyB1c3VhbGx5IG5vdCB0cml2aWFsIGFuZCBpbnN0ZWFkLCBmb3IgZXhhbXBsZSwgYSBNYXJrb3YgY2hhaW4KIycgTW9udGUgQ2FybG8gYWxnb3JpdGhtIGlzIHVzZWQuIFdlIGNhbiB2YWxpZGF0ZSB0aGUgYWxnb3JpdGhtIGFuZAojJyBpdHMgaW1wbGVtZW50YXRpb24gdXNlZCB0byBzYW1wbGUgZnJvbSAkXHBpKFx0aGV0YScnfHkpJCBieQojJyBjaGVja2luZyB0aGF0IHRoZSBzYW1wbGVzIG9idGFpbmVkIGhhdmUgdGhlIHNhbWUgZGlzdHJpYnV0aW9uIGFzCiMnICRcdGhldGEnJCAoY29uZGl0aW9uYWxseSBvbiAkeSkkLgojJyAKIycgQENvb2srR2VsbWFuK1J1YmluOjIwMDYgb3BlcmF0aW9uYWxpemUgdGhlIGFwcHJvYWNoIGJ5IGRyYXdpbmcKIycgJFx0aGV0YSdfaSQgZnJvbSAkXHBpKFx0aGV0YScpJCwgZ2VuZXJhdGluZyBkYXRhICR5X2kgXHNpbQojJyBccGkoeV9pfFx0aGV0YSdfaSkkIGFuZCB0aGVuIHVzaW5nIHRoZSBhbGdvcml0aG0gdG8gYmUgdmFsaWRhdGVkIHRvCiMnIGRyYXcgYSBzYW1wbGUgJFx0aGV0YScnXzEsXGxkb3RzLFx0aGV0YScnX1MgXHNpbQojJyBccGkoXHRoZXRhJyd8eV9pKSQuIElmIHRoZSBhbGdvcml0aG0gYW5kIGl0cyBpbXBsZW1lbnRhdGlvbiBhcmUKIycgY29ycmVjdCwgdGhlbiAkXHRoZXRhJ19pLFx0aGV0YScnXzEsXGxkb3RzLFx0aGV0YScnX1MkIGNvbmRpdGlvbmFsCiMnIG9uICR5X2kkIGFyZSBkcmF3cyBmcm9tIHRoZSBzYW1lCiMnIGRpc3RyaWJ1dGlvbi4gQENvb2srR2VsbWFuK1J1YmluOjIwMDYgcHJvcG9zZSB0byBjb21wdXRlCiMnIGVtcGlyaWNhbCBQSVQgdmFsdWVkIGZvciAkXHRoZXRhJ19pJCB0aGF0IHRoZXkgc2hvdyB0byBiZSB1bmlmb3JtbHkKIycgZGlzdHJpYnV0ZWQgZ2l2ZW4gJFMgXHRvIFxpbmZ0eSQuIFRoZSBwcm9jZXNzIGlzIHJlcGVhdGVkIGZvcgojJyAkaT0xLFxsZG90cyxOJCBhbmQgJE4kIGVtcGlyaWNhbCBQSVQgdmFsdWVzIGFyZSB1c2VkIGZvciB0ZXN0aW5nLgojJyBAQ29vaytHZWxtYW4rUnViaW46MjAwNiBwcm9wb3NlIHRvIHVzZSAkXGNoaV4yJC10ZXN0IGZvcgojJyB0aGUgaW52ZXJzZSBvZiB0aGUgbm9ybWFsIENERiBvZiB0aGUgZW1waXJpY2FsIFBJVCB2YWx1ZXMuIEhvd2V2ZXIsCiMnIHdpdGggZmluaXRlICRTJCB0aGlzIGFwcHJvYWNoIGRvZXNuJ3QgY29ycmVjdGx5IHRha2UgaW50byBhY2NvdW50CiMnIHRoZSBkaXNjcmV0ZW5lc3Mgb3IgdGhlIGVmZmVjdCBvZiBjb3JyZWxhdGVkIHNhbXBsZSBmcm9tIE1hcmtvdgojJyBjaGFpbiBAR2VsbWFuOmNvcnJlY3Rpb24uCiMnIAojJyBCeSB0aGlubmluZyAkXHRoZXRhXzFeeycnfSxcbGRvdHMsXHRoZXRhX1NeeycnfSQgdG8gYmUKIycgYXBwcm94aW1hdGVseSBpbmRlcGVuZGVudCwgdGhlIHVuaWZvcm1pdHkgb2YgZW1waXJpY2FsIFBJVCB2YWx1ZXMKIycgY2FuIGJlIHRlc3RlZCB3aXRoIHRoZSBhcHByb2FjaCBwcmVzZW50ZWQgaW4KIycgU8OkaWx5bm9qYStCdWVya25lcitWZWh0YXJpOjIwMjAuCiMnCiMnICMjIFNpbXVsYXRpb24gYmFzZWQgY2FsaWJyYXRpb24gY29uZGl0aW9uYWwgb24gb2JzZXJ2ZWQgZGF0YQojJyAKIycgV2hlbiB1c2luZyB3ZWFrbHkgaW5mb3JtYXRpdmUgcHJpb3JzLCBtb3N0IG9mIHRoZSBwcmlvciBtYXNzIGNhbiBiZQojJyBpbiB0aGUgcmVnaW9uIG9mIHRoZSBwYXJhbWV0ZXIgc3BhY2Ugd2hlcmUgdGhlIGluZmVyZW5jZSB3b3JrcwojJyB3ZWxsLCBidXQgYSBzbWFsbCBhbW91bnQgb2YgcHJpb3IgbWFzcyBjYW4gYWxzbyBiZSBpbiB0aGUgcmVnaW9ucwojJyB3aGVyZSBpbmZlcmVuY2UgaXMgbGlrZWx5IHRvIGZhaWwuIFdlIGNvdWxkIHVwZGF0ZSB0aGUgcHJpb3IgdG8KIycgYXZvaWQgc3VjaCByZWdpb25zLCBidXQgaWYgdGhlIHBvc3RlcmlvciBnaXZlbiBvYnNlcnZlZCBkYXRhIGlzCiMnIGNvbmNlbnRyYXRlZCBmYXIgZnJvbSB0aGUgcHJvYmxlbWF0aWMgcmVnaW9ucyB3ZSBjb3VsZCBpbnN0ZWFkCiMnIGZvY3VzIG9uIGFzc2Vzc2luZyB3aGV0aGVyIHRoZSBpbmZlcmVuY2Ugd29ya3MgYXJvdW5kIHRoZQojJyBwb3N0ZXJpb3IuCiMnCiMnIENvbnNpZGVyaW5nIHRoYXQgZ2l2ZW4gdGhlIHNlcXVlbnRpYWwgdXBkYXRlIHJ1bGUgaW4gQmF5ZXNpYW4KIycgYXBwcm9hY2gsIGFuIG9sZCBwb3N0ZXJpb3IgY2FuIGJlIGEgbmV3IHByaW9yIGFuZCB3ZSBjYW4gbmF0dXJhbGx5CiMnIGNvbnNpZGVyIFNCQyBjb25kaXRpb25hbCBvbiB0aGUgb2JzZXJ2ZWQgZGF0YSAkeV97XG1hdGhybXtvYnN9fSQuCiMnIFRodXMsIHdlIG9wZXJhdGlvbmFsaXplIHRoZSBhcHByb2FjaCBieSBkcmF3aW5nICRcdGhldGEnX2kkIGZyb20KIycgJFxwaShcdGhldGEnIHwgeV97XG1hdGhybXtvYnN9fSkkLCBnZW5lcmF0aW5nIG5ldyBkYXRhICR5X2kgXHNpbQojJyBccGkoeV9pfFx0aGV0YSdfaSkkIGFuZCB0aGVuIHVzaW5nIHRoZSBhbGdvcml0aG0gdG8gYmUgdmFsaWRhdGVkIHRvCiMnIGRyYXcgYSBzYW1wbGUgJFx0aGV0YScnXzEsXGxkb3RzLFx0aGV0YScnX1MgXHNpbQojJyBccGkoXHRoZXRhJycgfCB5X2ksIHlfe1xtYXRocm17b2JzfX0pJC4gSWYgdGhlIGFsZ29yaXRobSBhbmQgaXRzCiMnIGltcGxlbWVudGF0aW9uIGFyZSBjb3JyZWN0LCB0aGVuCiMnICRcdGhldGEnX2ksXHRoZXRhJydfMSxcbGRvdHMsXHRoZXRhJydfUyQgY29uZGl0aW9uYWwgb24gJHlfaSQgYW5kCiMnICR5X3tcbWF0aHJte29ic319JCBhcmUgZHJhd3MgZnJvbSB0aGUgc2FtZSBkaXN0cmlidXRpb24uCiMnCiMnIC0gSW4gcHJpb3IgU0JDLCB0aGUgcHJpb3IgZm9ybXVsYXRlZCBzbyB0aGF0IGl0IGlzIGVhc3kgdG8gZHJhdwojJyAgIGV4YWN0bHkgZnJvbSB0aGUgcHJpb3IgKGFuZCB3ZSBhc3N1bWUgbm8gbWlzdGFrZXMgYXJlIG1hZGUgd2hlbgojJyAgIGdlbmVyYXRpbmcgZHJhd3MgZnJvbSB0aGUgcHJpb3IpLCBhbmQgZXhhY3QgcHJpb3IgZHJhd3MgYXJlCiMnICAgY29tcGFyZWQgdG8gZHJhd3Mgb2J0YWluZWQgYnkgdGhlIGFwcHJveGltYXRlIGluZmVyZW5jZSBhbGdvcml0aG0KIycgICAodGhlIGFwcHJvYWNoIGNhbiBhbHNvIGRldGVjdCBtaXN0YWtlcyBpbiB0aGUgbW9kZWwgY29kZSB1c2VkIGluCiMnICAgdGhlIGluZmVyZW5jZSkuCiMnIC0gSWYgd2Ugd291bGQgYmUgYWJsZSB0byBnZXQgZXhhY3QgZHJhd3MgZnJvbSB0aGUgcG9zdGVyaW9yLCB3ZQojJyAgIGNvdWxkIGRpcmVjdGx5IGNvbXBhcmUgdGhlc2UgZXhhY3QgZHJhd3MgdG8gYW55IGFwcHJveGltYXRlCiMnICAgaW5mZXJlbmNlIHJlc3VsdCwgYW5kIHBvc3RlcmlvciBTQkMgaXMgbm90IG5lZWRlZC4KIycgLSBJbiBwb3N0ZXJpb3IgU0JDLCB3ZSBhcmUgY29tcGFyaW5nIHRoZSBzYW1lIGFsZ29yaXRobSBkcmF3aW5nCiMnICAgZnJvbSB0aGUgb3JpZ2luYWwgcG9zdGVyaW9yIGFuZCB0aGUgdXBkYXRlZCBwb3N0ZXJpb3IuIElmIHRoZQojJyAgIGFsZ29yaXRobSBpcyBub3QgY29uc2lzdGVudCB3aGVuIG9ic2VydmluZyBtb3JlIGRhdGEsIFNCQyBtYXkgYmUKIycgICBhYmxlIHRvIGRldGVjdCB0aGlzICh3aXRoIGZpbml0ZSBudW1iZXIgb2YgU0JDIGl0ZXJhdGlvbnMgYW5kCiMnICAgZmluaXRlIHNhbXBsZSBzaXplcywgd2UgbWF5IG1pc3Mgc21hbGwgZGlzY3JlcGFuY2llcykuCiMnIC0gSXQgaXMgcG9zc2libGUgdGhhdCBpbmZlcmVuY2UgY291bGQgd29yayBnaXZlbiB0aGUgb2JzZXJ2ZWQgZGF0YSwKIycgICBidXQgbm90IGFueW1vcmUgd2l0aCBhZGRpdGlvbmFsIGRhdGEuIFRoZSBkaWZmZXJlbmNlcyBpbiB0aGUKIycgICBzaGFwZSBvZiB0aGUgcG9zdGVyaW9yIGdpdmVuIHRoZSBvYnNlcnZlZCBkYXRhIGFuZCB0aGUgbmV3CiMnICAgcG9zdGVyaW9ycyBpbiBwb3N0ZXJpb3IgU0JDIGFyZSBsaWtlbHkgdG8gYmUgc21hbGxlciB0aGFuIHRoZQojJyAgIGRpZmZlcmVuY2VzIGluIHRoZSBzaGFwZSBvZiBkaWZmZXJlbnQgcG9zdGVyaW9ycyBpbiB0aGUgcHJpb3IgU0JDCiMnICAgYXBwcm9hY2guCiMnCiMrIHNldHVwLCBpbmNsdWRlPUZBTFNFCmtuaXRyOjpvcHRzX2NodW5rJHNldChtZXNzYWdlPUZBTFNFLCBlcnJvcj1GQUxTRSwgd2FybmluZz1GQUxTRSwgY29tbWVudD1OQSwgY2FjaGU9RkFMU0UpCiMrIGxvYWRfcGFja2FnZXMsIGVjaG89RkFMU0UKbGlicmFyeShjbWRzdGFucikKbGlicmFyeShwb3N0ZXJpb3IpCmxpYnJhcnkoZHBseXIpCmxpYnJhcnkobGF0ZXgyZXhwKQpsaWJyYXJ5KGdncGxvdDIpCmxpYnJhcnkoYmF5ZXNwbG90KQp0aGVtZV9zZXQoYmF5ZXNwbG90Ojp0aGVtZV9kZWZhdWx0KGJhc2VfZmFtaWx5ID0gInNhbnMiKSkKCiMnICMgbm9ybWFsKG11LCAxKSBtb2RlbAojJwojJyBXZSBzdGFydCBieSBpbGx1c3RyYXRpbmcgdGhlIGlkZWEgb2YgcHJpb3IgU0JDIGFuZCBwb3N0ZXJpb3IgU0JDCiMnIHVzaW5nIGEgc2ltcGxlICRcbWF0aHJte25vcm1hbH0oXG11LCAxKSQgbW9kZWwuIEdpdmVuIHByaW9yIGRyYXdzCiMnIG9mICRcbXUkLCB3ZSBnZW5lcmF0ZSBkYXRhIHNldHMgd2l0aCAkMTAkIG9ic2VydmF0aW9ucy4KIycgCiMnICMjIElsbHVzdHJhdGlvbiBvZiBwcmlvciBTQkMKIycKIycgUHJpb3IgcGFyYW1ldGVycwptdTA9MAp0YXUwPTEwCiMnIFBsb3QgdGhlIHByaW9yCnAwID0gZ2dwbG90KGRhdGEgPSBkYXRhLmZyYW1lKHggPSBjKC00MCwgNDApKSwgYWVzKHgpKSArCiAgc3RhdF9mdW5jdGlvbihmdW4gPSBkbm9ybSwgbiA9IDEwMSwgYXJncyA9IGxpc3QobWVhbiA9IG11MCwgc2QgPSB0YXUwKSwgbGluZXR5cGU9J2Rhc2hlZCcpICsKICB0aGVtZShheGlzLnRleHQueSA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICBheGlzLmxpbmUueT1lbGVtZW50X2JsYW5rKCksCiAgICAgICAgYXhpcy50aWNrcy55PWVsZW1lbnRfYmxhbmsoKSkrCiAgeWxhYignJykgCnAwCgojJyBPYnNlcnZhdGlvbiBtb2RlbCBzY2FsZQpzaWdtYT0xCiMnIE51bWJlciBvZiBvYnNlcnZhdGlvbnMKTj0xMAoKIycgUnVuIHNpbXVsYXRpb25zCnBwID0gcDAKZm9yIChpIGluIDE6MTApIHsKICBzZXQuc2VlZCgxMDAwK2kpCiAgIyBkcmF3IGZyb20gdGhlIHByaW9yCiAgbXVnPXJub3JtKDEsIG1lYW49bXUwLCBzZD10YXUwKQogICMgZ2VuZXJhdGUgZGF0YSBmcm9tIHRoZSBwcmVkaWN0aXZlIGRpc3RyaWJ1dGlvbiBnaXZlbiB0aGUgcGFyYW1ldGVyIHZhbHVlIHNhbXBsZWQgZnJvbSB0aGUgcHJpb3IKICB5Zz1ybm9ybShOLCBtZWFuPW11Zywgc2Q9c2lnbWEpCiAgIyBwb3N0ZXJpb3IKICB5YmFyPW1lYW4oeWcpCiAgbXVwPShtdTAvdGF1MF4yK04qeWJhci9zaWdtYV4yKS8oMS90YXUwXjIrTi9zaWdtYV4yKQogIHRhdXA9c3FydCgxLygxL3RhdTBeMitOL3NpZ21hXjIpKQogICMgZHJhdyBmcm9tIHRoZSBwb3N0ZXJpb3IKICBtdXBnPXJub3JtKDEsIG1lYW49bXVwLCBzZD10YXVwKQogICMgYWRkIHByaW9yIGRyYXcsIHBvc3RlcmlvciwgYW5kIHBvc3RlcmlvciBkcmF3IHRvIHRoZSBwbG90CiAgcHAgPSBwcCArCiAgICBzdGF0X2Z1bmN0aW9uKGZ1biA9IGZ1bmN0aW9uKC4uLikgZG5vcm0oLi4uKS8zMywgbiA9IDEwMDEsIGFyZ3MgPSBsaXN0KG1lYW4gPSBtdXAsIHNkID0gdGF1cCksIGFscGhhPTAuMykgKwogICAgYW5ub3RhdGUoZ2VvbSA9ICJwb2ludCIsIHg9bXVnLCB5PTAsIGNvbG9yPSdyZWQnLCBhbHBoYT0wLjkpKwogICAgYW5ub3RhdGUoZ2VvbSA9ICJwb2ludCIsIHg9bXVwZywgeT0wLCBjb2xvcj0nYmx1ZScsIGFscGhhPTAuOSkKfQpwcAoKIycgVGhlIHR5cGljYWwgZmVhdHVyZSBvZiBwcmlvciBTQkMgaXMgdmlzaWJsZSwgdGhhdCBpcywgdGhlCiMnIGNvbmRpdGlvbmFsIHBvc3RlcmlvcnMgYXJlIG11Y2ggbW9yZSBuYXJyb3cgdGhhbiB0aGUgcHJpb3IKIycgZGlzdHJpYnV0aW9uLiBXZSBpbGx1c3RyYXRlIGxhdGVyIGhvdyB0aGlzIGFmZmVjdHMgaG93IHRoZSBwcmlvcgojJyBhbmQgY29uZGl0aW9uYWwgcG9zdGVyaW9yIGRyYXdzIHNob3VsZCBiZSBjb21wYXJlZC4KIycgCiMnICMjIElsbHVzdHJhdGlvbiBvZiBwb3N0ZXJpb3IgU0JDCiMnCiMnIFdlIGFzc3VtZSB3ZSBoYXZlIG9ic2VydmVkIDEwIG9ic2VydmF0aW9ucyB3aXRoIG1lYW4gJDguNiQuIEdpdmVuCiMnIHBvc3RlcmlvciBkcmF3cyBvZiAkXG11JCBnaXZlbiAkeV9cbWF0aHJte29ic30kLCB3ZSBnZW5lcmF0ZQojJyBhZGRpdGlvbmFsIGRhdGEgc2V0cyB3aXRoICQxMCQgb2JzZXJ2YXRpb25zIGVhY2guIEluIHBvc3RlcmlvciBTQkMsCiMnIHdlIHJ1biB0aGUgaW5mZXJlbmNlIGdpdmVuIG9yaWdpbmFsICR5X1xtYXRocm17b2JzfSQgYW5kIG5ldwojJyBhZGRpdGlvbmFsIGRhdGEuCiMnIAojJyBQcmlvcgptdTA9MAp0YXUwPTEwCiMnIE9ic2VydmF0aW9uIG1vZGVsIHNjYWxlCnNpZ21hPTEKIycgTnVtYmVyIG9mIG9ic2VydmF0aW9ucwpOPTEwCiMnIE9ic2VydmVkIGRhdGEgbWVhbgp5YmFyPTguNgojJyBQb3N0ZXJpb3IgZ2l2ZW4gdGhlIG9ic2VydmVkIGRhdGEKbXVwPShtdTAvdGF1MF4yK04qeWJhci9zaWdtYV4yKS8oMS90YXUwXjIrTi9zaWdtYV4yKQp0YXVwPXNxcnQoMS8oMS90YXUwXjIrTi9zaWdtYV4yKSkKIycgUGxvdCB0aGUgcG9zdGVyaW9yCnBwMSA9IGdncGxvdChkYXRhID0gZGF0YS5mcmFtZSh4ID0gYyg3LjQsIDkuNykpLCBhZXMoeCkpICsKICBzdGF0X2Z1bmN0aW9uKGZ1biA9IGRub3JtLCBuID0gMTAxLCBhcmdzID0gbGlzdChtZWFuID0gbXVwLCBzZCA9IHRhdXApLCBsaW5ldHlwZT0nZGFzaGVkJykgKwogIHRoZW1lKGF4aXMudGV4dC55ID0gZWxlbWVudF9ibGFuaygpLAogICAgICAgIGF4aXMubGluZS55PWVsZW1lbnRfYmxhbmsoKSwKICAgICAgICBheGlzLnRpY2tzLnk9ZWxlbWVudF9ibGFuaygpKSsKICB5bGFiKCcnKSAKcHAxCgojJyBSdW4gc2ltdWxhdGlvbnMgCnBwMiA9IHBwMQpmb3IgKGkgaW4gMToxMCkgewogIHNldC5zZWVkKDEwMDAraSkKICAjIGRyYXcgZnJvbSB0aGUgcG9zdGVyaW9yCiAgbXVnMj1ybm9ybSgxLCBtZWFuPW11cCwgc2Q9dGF1cCkKICAjIGdlbmVyYXRlIGRhdGEgZnJvbSB0aGUgcHJlZGljdGl2ZSBkaXN0cmlidXRpb24gZ2l2ZW4gdGhlIHBhcmFtZXRlciB2YWx1ZSBzYW1wbGVkIGZyb20gdGhlIHBvc3RlcmlvcgogIHlnMj1ybm9ybShOLCBtZWFuPW11ZzIsIHNkPXNpZ21hKQogICMgc2Vjb25kIHBvc3RlcmlvcgogIHliYXIyPW1lYW4oeWcyKQogIG11cDI9KG11cC90YXVwXjIrTip5YmFyMi9zaWdtYV4yKS8oMS90YXVwXjIrTi9zaWdtYV4yKQogIHRhdXAyPXNxcnQoMS8oMS90YXVwXjIrTi9zaWdtYV4yKSkKICAjIGRyYXcgZnJvbSB0aGUgc2Vjb25kIHBvc3RlcmlvcgogIG11cGcyPXJub3JtKDEsIG1lYW49bXVwMiwgc2Q9dGF1cDIpCiAgIyBhZGQgcG9zdGVyaW9yIGRyYXcsIHNlY29uZCBwb3N0ZXJpb3IsIGFuZCBkcmF3IGZyb20gdGhlIHNlY29uZCBwb3N0ZXJpb3IgdG8gdGhlIHBsb3QKICBwcDIgPSBwcDIgKwogICAgc3RhdF9mdW5jdGlvbihmdW4gPSBmdW5jdGlvbiguLi4pIGRub3JtKC4uLikvMiwgbiA9IDEwMDEsIGFyZ3MgPSBsaXN0KG1lYW4gPSBtdXAyLCBzZCA9IHRhdXAyKSwgYWxwaGE9MC4zKSArCiAgICBhbm5vdGF0ZShnZW9tID0gInBvaW50IiwgeD1tdWcyLCB5PTAsIGNvbG9yPSdyZWQnLCBhbHBoYT0wLjkpKwogICAgYW5ub3RhdGUoZ2VvbSA9ICJwb2ludCIsIHg9bXVwZzIsIHk9MCwgY29sb3I9J2JsdWUnLCBhbHBoYT0wLjkpCn0KcHAyCgojJyBXZSBzZWUgdGhlIHR5cGljYWwgZmVhdHVyZSBvZiBwb3N0ZXJpb3IgU0JDLCB0aGF0IGlzLCB0aGUKIycgY29uZGl0aW9uYWwgcG9zdGVyaW9ycyBhcmUgb25seSBzbGlnaHRseSBtb3JlIG5hcnJvdyB0aGFuIHRoZQojJyBvcmlnaW5hbCBwb3N0ZXJpb3IgZGlzdHJpYnV0aW9uIChmYWN0b3Igb2YgJFxzcXJ0ezJ9KS4gV2UKIycgaWxsdXN0cmF0ZSBsYXRlciBob3cgdGhpcyBhZmZlY3RzIGhvdyB0aGUgcG9zdGVyaW9yIGFuZCBjb25kaXRpb25hbAojJyBwb3N0ZXJpb3IgZHJhd3Mgc2hvdWxkIGJlIGNvbXBhcmVkLgojJwojJyAjIyBQcmlvciBTQkMKIycKIycgV2Ugbm93IGlsbHVzdHJhdGUgdGhlIGJlaGF2aW9yIG9mIHByaW9yIFNCQyBnaXZlbiBhIGNvcnJlY3QgYW5kCiMnIGluY29ycmVjdCBjb25kaXRpb25hbCBwb3N0ZXJpb3IgaW5mZXJlbmNlLgojJyAKIycgIyMjIENvcnJlY3QgcG9zdGVyaW9yCm11Z3MgPSBtdXBzID0gcGl0cyA9IG51bWVyaWMoKQpwcCA9IHAwCmZvciAoaSBpbiAxOjEwMDApIHsKICBzZXQuc2VlZCgxMDAwK2kpCiAgbXVnPXJub3JtKDEsIG1lYW49bXUwLCBzZD10YXUwKQogIG11Z3NbaV09bXVnWzFdCiAgeWc9cm5vcm0oTiwgbWVhbj1tdWcsIHNkPXNpZ21hKQogIHliYXI9bWVhbih5ZykKICBtdXA9KG11MC90YXUwXjIrTip5YmFyL3NpZ21hXjIpLygxL3RhdTBeMitOL3NpZ21hXjIpCiAgdGF1cD1zcXJ0KDEvKDEvdGF1MF4yK04vc2lnbWFeMikpCiAgbXVwZz1ybm9ybSgxMDAwLCBtZWFuPW11cCwgc2Q9dGF1cCkKICBtdXBzW2ldPW11cGdbMV0KICBwaXRzW2ldPW1lYW4obXVwczxtdWcpCn0KZGY9ZGF0YS5mcmFtZShtdWdzLG11cHMscGl0cykKCnAyPWdncGxvdChkYXRhPWRmLGFlcyh4PW11Z3MseT1tdXBzKSkrCiAgZ2VvbV9wb2ludChhbHBoYT0wLjUsY29sb3I9J2JsdWUnKSsKICBnZW9tX2FibGluZSgpKwogIGxhYnMoeD1UZVgoJyRcXG11XCcgXFxzaW0gcChcXG11KSQnKSx5PVRlWCgnJFxcbXVcJ1wnIFxcc2ltIHAoXFxtdSB8IHlfaSkkJykpCnBsaW1zID0gcmFuZ2UoYyhnZ3Bsb3RfYnVpbGQocDIpJGxheW91dCRwYW5lbF9wYXJhbXNbWzFdXSR4LnJhbmdlLAogICAgICAgICAgICAgICAgIGdncGxvdF9idWlsZChwMikkbGF5b3V0JHBhbmVsX3BhcmFtc1tbMV1dJHkucmFuZ2UpKQpwMitsaW1zKHg9cGxpbXMseT1wbGltcykKIycKIycgUHJpb3IgZHJhd3MgYW5kIGNvbmRpdGlvbmFsIHBvc3RlcmlvciBkcmF3cyBhcmUgaGlnaGx5IGNvcnJlbGF0ZWQuCiMnCmdncGxvdChkYXRhPWRmLGFlcyh4PXNvcnQobXVncykseT1zb3J0KG11cHMpKSkrCiAgZ2VvbV9wb2ludChhbHBoYT0uMyxjb2xvcj0nYmx1ZScpKwogIGdlb21fYWJsaW5lKCkrCiAgbGFicyh4PVRlWCgnc29ydGVkICRcXG11XCcgXFxzaW0gcChcXG11KSQnKSx5PVRlWCgnc29ydGVkICRcXG11XCdcJyBcXHNpbSBwKFxcbXUgfCB5X2kpJCcpKQojJwojJyBRUS1wbG90IGFsc28gbG9va3MgZ29vZC4KIycgCmdncGxvdChkYXRhPWRmLGFlcyh4PXNlcSgwLDEsbGVuZ3RoLm91dD0xMDAwKSx5PXNvcnQocGl0cykpKSsKICBnZW9tX2xpbmUoY29sb3I9J2JsdWUnLHNpemU9MikrCiAgZ2VvbV9hYmxpbmUoKSsKICBsYWJzKHg9J1VuaWZvcm0nLHk9J1BJVCcpCiMnCiMnIEVDREYgb2YgcHJvYmFiaWxpdHkgaW50ZWdyYWwgdHJhbnNmb3JtYXRpb24gKFBJVCkgbG9va3MgYWxzbyBnb29kCiMnIGFzIGl0IHNob3VsZC4KIycgCgojJyAjIyMgSW5jb3JyZWN0IHBvc3RlcmlvcgojJwojJyBIZXJlIHdlIGhhdmUgaW5jb3JyZWN0IGluZmVyZW5jZSwgc28gdGhhdCBwb3N0ZXJpb3Igc2NhbGUgZm9ybXVsYQojJyBpcyBtaXNzaW5nIHRoZSBzcXVhcmUgcm9vdCAoYSBtaXN0YWtlIHdlIGFjdHVhbGx5IGZpcnN0IG1hZGUpLgojJyAKbXVncyA9IG11cHMgPSBwaXRzID0gbnVtZXJpYygpCnBwID0gcDAKZm9yIChpIGluIDE6MTAwMCkgewogIHNldC5zZWVkKDEwMDAraSkKICBtdWc9cm5vcm0oMSwgbWVhbj1tdTAsIHNkPXRhdTApCiAgbXVnc1tpXT1tdWdbMV0KICB5Zz1ybm9ybShOLCBtZWFuPW11Zywgc2Q9c2lnbWEpCiAgeWJhcj1tZWFuKHlnKQogIG11cD0obXUwL3RhdTBeMitOKnliYXIvc2lnbWFeMikvKDEvdGF1MF4yK04vc2lnbWFeMikKICAjIGNvcnJlY3QKICAjIHRhdXA9c3FydCgxLygxL3RhdTBeMitOL3NpZ21hXjIpKQogICMgd3JvbmcKICB0YXVwPSgxLygxL3RhdTBeMitOL3NpZ21hXjIpKQogIG11cGc9cm5vcm0oMTAwMCwgbWVhbj1tdXAsIHNkPXRhdXApCiAgbXVwc1tpXT1tdXBnWzFdCiAgcGl0c1tpXT1tZWFuKG11cGc8bXVnKQp9CmRmPWRhdGEuZnJhbWUobXVncyxtdXBzLHBpdHMpCgpwMj1nZ3Bsb3QoZGF0YT1kZixhZXMoeD1tdWdzLHk9bXVwcykpKwogIGdlb21fcG9pbnQoYWxwaGE9MC41LGNvbG9yPSdibHVlJykrCiAgZ2VvbV9hYmxpbmUoKSsKICBsYWJzKHg9VGVYKCckXFxtdVwnIFxcc2ltIHAoXFxtdSkkJykseT1UZVgoJyRcXG11XCdcJyBcXHNpbSBwKFxcbXUgfCB5X2kpJCcpKQpwbGltcyA9IHJhbmdlKGMoZ2dwbG90X2J1aWxkKHAyKSRsYXlvdXQkcGFuZWxfcGFyYW1zW1sxXV0keC5yYW5nZSwKICAgICAgICAgICAgICAgICBnZ3Bsb3RfYnVpbGQocDIpJGxheW91dCRwYW5lbF9wYXJhbXNbWzFdXSR5LnJhbmdlKSkKcDIrbGltcyh4PXBsaW1zLHk9cGxpbXMpCiMnCiMnIEFzIHRoZSBjb25kaXRpb25hbCBwb3N0ZXJpb3JzIGFyZSB2ZXJ5IG5hcnJvdywgdGhlIGRyYXdzIGZyb20gdGhlCiMnIGNvbmRpdGlvbmFsIHBvc3RlcmlvcnMgYXJlIGhpZ2hseSBjb3JyZWxhdGVkIHdpdGggdGhlIHByaW9yIGRyYXdzCiMnIGFuZCB3ZSBjYW4ndCBzZWUgYW55dGhpbmcgYmVpbmcgd3JvbmcuCiMnIApnZ3Bsb3QoZGF0YT1kZixhZXMoeD1zb3J0KG11Z3MpLHk9c29ydChtdXBzKSkpKwogIGdlb21fcG9pbnQoYWxwaGE9LjMsY29sb3I9J2JsdWUnKSsKICBnZW9tX2FibGluZSgpKwogIGxhYnMoeD1UZVgoJ3NvcnRlZCAkXFxtdVwnIFxcc2ltIHAoXFxtdSkkJykseT1UZVgoJ3NvcnRlZCAkXFxtdVwnXCcgXFxzaW0gcChcXG11IHwgeV9pKSQnKSkKIycKIycgUVEtcGxvdCBhbHNvIGxvb2tzIGdvb2QuCiMnIApnZ3Bsb3QoZGF0YT1kZixhZXMoeD1zZXEoMCwxLGxlbmd0aC5vdXQ9MTAwMCkseT1zb3J0KHBpdHMpKSkrCiAgZ2VvbV9saW5lKGNvbG9yPSdibHVlJyxzaXplPTIpKwogIGdlb21fYWJsaW5lKCkrCiAgbGFicyh4PSdVbmlmb3JtJyx5PSdQSVQnKQojJwojJyBQSVQgcGxvdCBsb29rcyB0ZXJyaWJsZS4gVGhlIGNvbmRpdGlvbmFsIHBvc3RlcmlvcnMgYXJlIHRvbyBuYXJyb3csCiMnIGFuZCB0aHVzIFBJVCB2YWx1ZXMgYXJlIG5vdCB1bmlmb3JtbHkgZGlzdHJpYnV0ZWQuCiMnIAoKIycgIyMgUG9zdGVyaW9yIFNCQwojJwojJyBXZSBub3cgaWxsdXN0cmF0ZSB0aGUgYmVoYXZpb3Igb2YgcG9zdGVyaW9yIFNCQyBnaXZlbiBhIGNvcnJlY3QgYW5kCiMnIGluY29ycmVjdCBjb25kaXRpb25hbCBwb3N0ZXJpb3IgaW5mZXJlbmNlLgojJyAKIycgIyMjIENvcnJlY3QgcG9zdGVyaW9yCiMnIAojJyBPYnNlcnZlZCBkYXRhIG1lYW4KeWJhcj04LjYKIycgUG9zdGVyaW9yIGdpdmVuIHRoZSBvYnNlcnZlZCBkYXRhCm11cD0obXUwL3RhdTBeMitOKnliYXIvc2lnbWFeMikvKDEvdGF1MF4yK04vc2lnbWFeMikKdGF1cD1zcXJ0KDEvKDEvdGF1MF4yK04vc2lnbWFeMikpCiMnIFJ1biBzaW11bGF0aW9ucyAKbXVnMnMgPSBtdXAycyA9IHBpdDJzID0gbnVtZXJpYygpCnBwMiA9IHBwMQpmb3IgKGkgaW4gMToxMDAwKSB7CiAgc2V0LnNlZWQoMTAwMCtpKQogICMgZHJhdyBmcm9tIHRoZSBwb3N0ZXJpb3IKICBtdWcyPXJub3JtKDEsIG1lYW49bXVwLCBzZD10YXVwKQogIG11ZzJzW2ldPW11ZzIKICAjIGdlbmVyYXRlIGRhdGEgZnJvbSB0aGUgcHJlZGljdGl2ZSBkaXN0cmlidXRpb24gZ2l2ZW4gdGhlIHBhcmFtZXRlciB2YWx1ZSBzYW1wbGVkIGZyb20gdGhlIHBvc3RlcmlvcgogIHlnMj1ybm9ybShOLCBtZWFuPW11ZzIsIHNkPXNpZ21hKQogICMgc2Vjb25kIHBvc3RlcmlvcgogIHliYXIyPW1lYW4oeWcyKQogIG11cDI9KG11cC90YXVwXjIrTip5YmFyMi9zaWdtYV4yKS8oMS90YXVwXjIrTi9zaWdtYV4yKQogIHRhdXAyPXNxcnQoMS8oMS90YXVwXjIrTi9zaWdtYV4yKSkKICAjIGRyYXcgZnJvbSB0aGUgc2Vjb25kIHBvc3RlcmlvcgogIG11cGcyPXJub3JtKDEwMDAsIG1lYW49bXVwMiwgc2Q9dGF1cDIpCiAgbXVwMnNbaV09bXVwZzJbMV0KICBwaXQyc1tpXT1tZWFuKG11cGcyPG11ZzIpCn0KZGY9ZGF0YS5mcmFtZShtdWcycyxtdXAycyxwaXQycykKCnAyPWdncGxvdChkYXRhPWRmLGFlcyh4PW11ZzJzLHk9bXVwMnMpKSsKICBnZW9tX3BvaW50KGFscGhhPTAuNSxjb2xvcj0nYmx1ZScpKwogIGdlb21fYWJsaW5lKCkrCiAgbGFicyh4PVRlWCgnJFxcbXVcJyBcXHNpbSBwKFxcbXUgfCB5X3tcXG1hdGhybXtvYnN9fSkkJykseT1UZVgoJyRcXG11XCdcJyBcXHNpbSBwKFxcbXUgfCB5X2ksIHlfe1xcbWF0aHJte29ic319KSQnKSkKcGxpbXMgPSByYW5nZShjKGdncGxvdF9idWlsZChwMikkbGF5b3V0JHBhbmVsX3BhcmFtc1tbMV1dJHgucmFuZ2UsCiAgICAgICAgICAgICAgICAgZ2dwbG90X2J1aWxkKHAyKSRsYXlvdXQkcGFuZWxfcGFyYW1zW1sxXV0keS5yYW5nZSkpCnAyK2xpbXMoeD1wbGltcyx5PXBsaW1zKQojJwojJyBQb3N0ZXJpb3IgZHJhd3MgYW5kIGNvbmRpdGlvbmFsIHBvc3RlcmlvciBkcmF3cyBhcmUgd2Vha2x5IGNvcnJlbGF0ZWQuCiMnIAoKZ2dwbG90KGRhdGE9ZGYsYWVzKHg9c29ydChtdWcycykseT1zb3J0KG11cDJzKSkpKwogIGdlb21fcG9pbnQoYWxwaGE9LjMsY29sb3I9J2JsdWUnKSsKICBnZW9tX2FibGluZSgpKwogIGxhYnMoeD1UZVgoJ3NvcnRlZCAkXFxtdVwnIFxcc2ltIHAoXFxtdSB8IHlfe1xcbWF0aHJte29ic319KSQnKSx5PVRlWCgnc29ydGVkICRcXG11XCdcJyBcXHNpbSBwKFxcbXUgfCB5X2ksIHlfe1xcbWF0aHJte29ic319KSQnKSkKIycKIycgUVEtcGxvdCBhbHNvIGxvb2tzIGdvb2QuCiMnIApnZ3Bsb3QoZGF0YT1kZixhZXMoeD1zZXEoMCwxLGxlbmd0aC5vdXQ9MTAwMCkseT1zb3J0KHBpdDJzKSkpKwogIGdlb21fbGluZShjb2xvcj0nYmx1ZScsc2l6ZT0yKSsKICBnZW9tX2FibGluZSgpKwogIGxhYnMoeD0nVW5pZm9ybScseT0nUElUJykKIycKIycgRUNERiBvZiBwcm9iYWJpbGl0eSBpbnRlZ3JhbCB0cmFuc2Zvcm1hdGlvbiAoUElUKSBsb29rcyBhbHNvIGdvb2QKIycgYXMgaXQgc2hvdWxkLgojJyAKIycgIyMjIEluY29ycmVjdCBwb3N0ZXJpb3IgMQojJyAKIycgSGVyZSB3ZSBoYXZlIGluY29ycmVjdCBpbmZlcmVuY2UsIHNvIHRoYXQgcG9zdGVyaW9yIHNjYWxlIGZvcm11bGEKIycgaXMgbWlzc2luZyB0aGUgc3F1YXJlIHJvb3QuCiMnIAojJyBPYnNlcnZlZCBkYXRhIG1lYW4KeWJhcj04LjYKIycgUG9zdGVyaW9yIGdpdmVuIHRoZSBvYnNlcnZlZCBkYXRhCm11cD0obXUwL3RhdTBeMitOKnliYXIvc2lnbWFeMikvKDEvdGF1MF4yK04vc2lnbWFeMikKdGF1cD0oMS8oMS90YXUwXjIrTi9zaWdtYV4yKSkKIycgUnVuIHNpbXVsYXRpb25zIAptdWcycyA9IG11cDJzID0gcGl0MnMgPSBudW1lcmljKCkKcHAyID0gcHAxCmZvciAoaSBpbiAxOjEwMDApIHsKICBzZXQuc2VlZCgxMDAwK2kpCiAgIyBkcmF3IGZyb20gdGhlIHBvc3RlcmlvcgogIG11ZzI9cm5vcm0oMSwgbWVhbj1tdXAsIHNkPXRhdXApCiAgbXVnMnNbaV09bXVnMgogICMgZ2VuZXJhdGUgZGF0YSBmcm9tIHRoZSBwcmVkaWN0aXZlIGRpc3RyaWJ1dGlvbiBnaXZlbiB0aGUgcGFyYW1ldGVyIHZhbHVlIHNhbXBsZWQgZnJvbSB0aGUgcG9zdGVyaW9yCiAgeWcyPXJub3JtKE4sIG1lYW49bXVnMiwgc2Q9c2lnbWEpCiAgIyBzZWNvbmQgcG9zdGVyaW9yCiAgeWJhcjI9bWVhbih5ZzIpCiAgbXVwMj0obXVwL3RhdXBeMitOKnliYXIyL3NpZ21hXjIpLygxL3RhdXBeMitOL3NpZ21hXjIpCiAgdGF1cDI9KDEvKDEvdGF1cF4yK04vc2lnbWFeMikpCiAgIyBkcmF3IGZyb20gdGhlIHNlY29uZCBwb3N0ZXJpb3IKICBtdXBnMj1ybm9ybSgxMDAwLCBtZWFuPW11cDIsIHNkPXRhdXAyKQogIG11cDJzW2ldPW11cGcyWzFdCiAgcGl0MnNbaV09bWVhbihtdXBnMjxtdWcyKQp9CmRmPWRhdGEuZnJhbWUobXVnMnMsbXVwMnMscGl0MnMpCgpwMiA9IGdncGxvdChkYXRhPWRmLGFlcyh4PW11ZzJzLHk9bXVwMnMpKSsKICBnZW9tX3BvaW50KGFscGhhPTAuNSxjb2xvcj0nYmx1ZScpKwogIGdlb21fYWJsaW5lKCkrCiAgbGFicyh4PVRlWCgnJFxcbXVcJyBcXHNpbSBwKFxcbXUgfCB5X3tcXG1hdGhybXtvYnN9fSkkJykseT1UZVgoJyRcXG11XCdcJyBcXHNpbSBwKFxcbXUgfCB5X2ksIHlfe1xcbWF0aHJte29ic319KSQnKSkKcGxpbXMgPC0gcmFuZ2UoYyhnZ3Bsb3RfYnVpbGQocDIpJGxheW91dCRwYW5lbF9wYXJhbXNbWzFdXSR4LnJhbmdlLAogICAgICAgICAgICAgICAgIGdncGxvdF9idWlsZChwMikkbGF5b3V0JHBhbmVsX3BhcmFtc1tbMV1dJHkucmFuZ2UpKQpwMitsaW1zKHg9cGxpbXMseT1wbGltcykKIycKIycgUG9zdGVyaW9yIGRyYXdzIGFuZCBjb25kaXRpb25hbCBwb3N0ZXJpb3IgZHJhd3MgYXJlIHdlYWtseSBjb3JyZWxhdGVkLCBidXQgCiMnIHRoZSBjb25kaXRpb25hbCBwb3N0ZXJpb3IgZHJhd3MgaGF2ZSBtdWNoIHNtYWxsZXIgdmFyaWFiaWxpdHkuCiMnIApnZ3Bsb3QoZGF0YT1kZixhZXMoeD1zb3J0KG11ZzJzKSx5PXNvcnQobXVwMnMpKSkrCiAgZ2VvbV9wb2ludChhbHBoYT0uMyxjb2xvcj0nYmx1ZScpKwogIGdlb21fYWJsaW5lKCkrCiAgbGFicyh4PVRlWCgnc29ydGVkICRcXG11XCcgXFxzaW0gcChcXG11IHwgeV97XFxtYXRocm17b2JzfX0pJCcpLHk9VGVYKCdzb3J0ZWQgJFxcbXVcJ1wnIFxcc2ltIHAoXFxtdSB8IHlfaSwgeV97XFxtYXRocm17b2JzfX0pJCcpKQojJwojJyBRUS1wbG90IGFsc28gc2hvd3MgdGhhdCB0aGUgY29uZGl0aW9uYWwgcG9zdGVyaW9yIGRyYXdzIGhhdmUgbXVjaAojJyBzbWFsbGVyIHZhcmlhYmlsaXR5LgojJyAKZ2dwbG90KGRhdGE9ZGYsYWVzKHg9c2VxKDAsMSxsZW5ndGgub3V0PTEwMDApLHk9c29ydChwaXQycykpKSsKICBnZW9tX2xpbmUoY29sb3I9J2JsdWUnLHNpemU9MikrCiAgZ2VvbV9hYmxpbmUoKSsKICBsYWJzKHg9J1VuaWZvcm0nLHk9J1BJVCcpCiMnCiMnIFBJVCBwbG90IGxvb2tzIGFsc28gdGVycmlibGUuIFRoZSBjb25kaXRpb25hbCBwb3N0ZXJpb3JzIGFyZSB0b28KIycgbmFycm93LCBhbmQgdGh1cyBQSVQgdmFsdWVzIGFyZSBub3QgdW5pZm9ybWx5IGRpc3RyaWJ1dGVkLgojJyAKCiMnICMjIyBJbmNvcnJlY3QgcG9zdGVyaW9yIDIKIycKIycgSGVyZSB3ZSdyZSBhZ2FpbiB1bmRlcmVzdGltYXRpbmcgdGhlIHBvc3RlcmlvciB2YXJpYW5jZSwgYnV0IGxlc3MKIycgdGhhbiBpbiB0aGUgZmlyc3QgaW5jb3JyZWN0IGluZmVyZW5jZSBleGFtcGxlLiBOb3cgd2UgY29tcHV0ZSB0aGUKIycgdmFyaWFuY2UgYXMgODAlIGZyb20gdGhlIHRydWUgcG9zdGVyaW9yIHZhcmlhbmNlLgojJyAKIycgT2JzZXJ2ZWQgZGF0YSBtZWFuCnliYXI9OC42CiMnIFBvc3RlcmlvciBnaXZlbiB0aGUgb2JzZXJ2ZWQgZGF0YQptdXA9KG11MC90YXUwXjIrTip5YmFyL3NpZ21hXjIpLygxL3RhdTBeMitOL3NpZ21hXjIpCnRhdXA9MC44KnNxcnQoMS8oMS90YXUwXjIrTi9zaWdtYV4yKSkKIycgUnVuIHNpbXVsYXRpb25zIAptdWcycyA9IG11cDJzID0gcGl0MnMgPSBudW1lcmljKCkKcHAyID0gcHAxCmZvciAoaSBpbiAxOjEwMDApIHsKICBzZXQuc2VlZCgxMDAwK2kpCiAgIyBkcmF3IGZyb20gdGhlIHBvc3RlcmlvcgogIG11ZzI9cm5vcm0oMSwgbWVhbj1tdXAsIHNkPXRhdXApCiAgbXVnMnNbaV09bXVnMgogICMgZ2VuZXJhdGUgZGF0YSBmcm9tIHRoZSBwcmVkaWN0aXZlIGRpc3RyaWJ1dGlvbiBnaXZlbiB0aGUgcGFyYW1ldGVyIHZhbHVlIHNhbXBsZWQgZnJvbSB0aGUgcG9zdGVyaW9yCiAgeWcyPXJub3JtKE4sIG1lYW49bXVnMiwgc2Q9c2lnbWEpCiAgIyBzZWNvbmQgcG9zdGVyaW9yCiAgeWJhcjI9bWVhbih5ZzIpCiAgbXVwMj0obXVwL3RhdXBeMitOKnliYXIyL3NpZ21hXjIpLygxL3RhdXBeMitOL3NpZ21hXjIpCiAgdGF1cDI9MC44KnNxcnQoMS8oMS90YXVwXjIrTi9zaWdtYV4yKSkKICAjIGRyYXcgZnJvbSB0aGUgc2Vjb25kIHBvc3RlcmlvcgogIG11cGcyPXJub3JtKDEwMDAsIG1lYW49bXVwMiwgc2Q9dGF1cDIpCiAgbXVwMnNbaV09bXVwZzJbMV0KICBwaXQyc1tpXT1tZWFuKG11cGcyPG11ZzIpCn0KZGY9ZGF0YS5mcmFtZShtdWcycyxtdXAycyxwaXQycykKCnAyPWdncGxvdChkYXRhPWRmLGFlcyh4PW11ZzJzLHk9bXVwMnMpKSsKICBnZW9tX3BvaW50KGFscGhhPTAuNSxjb2xvcj0nYmx1ZScpKwogIGdlb21fYWJsaW5lKCkrCiAgbGFicyh4PVRlWCgnJFxcbXVcJyBcXHNpbSBwKFxcbXUgfCB5X3tcXG1hdGhybXtvYnN9fSkkJykseT1UZVgoJyRcXG11XCdcJyBcXHNpbSBwKFxcbXUgfCB5X2ksIHlfe1xcbWF0aHJte29ic319KSQnKSkKcGxpbXMgPC0gcmFuZ2UoYyhnZ3Bsb3RfYnVpbGQocDIpJGxheW91dCRwYW5lbF9wYXJhbXNbWzFdXSR4LnJhbmdlLAogICAgICAgICAgICAgICAgIGdncGxvdF9idWlsZChwMikkbGF5b3V0JHBhbmVsX3BhcmFtc1tbMV1dJHkucmFuZ2UpKQpwMitsaW1zKHg9cGxpbXMseT1wbGltcykKIycKIycgUG9zdGVyaW9yIGRyYXdzIGFuZCBjb25kaXRpb25hbCBwb3N0ZXJpb3IgZHJhd3MgYXJlIHdlYWtseQojJyBjb3JyZWxhdGVkLiBJdCBpcyBkaWZmaWN1bHQgdG8gc2VlIGFueSBkaXNjcmVwYW5jeSBmcm9tIHRoaXMgcGxvdC4KIycgCmdncGxvdChkYXRhPWRmLGFlcyh4PXNvcnQobXVnMnMpLHk9c29ydChtdXAycykpKSsKICBnZW9tX3BvaW50KGFscGhhPS4zLGNvbG9yPSdibHVlJykrCiAgZ2VvbV9hYmxpbmUoKSsKICBsYWJzKHg9VGVYKCdzb3J0ZWQgJFxcbXVcJyBcXHNpbSBwKFxcbXUgfCB5X3tcXG1hdGhybXtvYnN9fSkkJykseT1UZVgoJ3NvcnRlZCAkXFxtdVwnXCcgXFxzaW0gcChcXG11IHwgeV9pLCB5X3tcXG1hdGhybXtvYnN9fSkkJykpCiMnCiMnIFFRLXBsb3QgaW5kaWNhdGVzIHByb2JsZW1zIGF0IHRhaWxzLiBUaGUgY29uZGl0aW9uYWwgcG9zdGVyaW9yCiMnIHNlZW1zIHRvIGJlIHNsaWdodGx5IHRvbyBuYXJyb3cuCiMnIApnZ3Bsb3QoZGF0YT1kZixhZXMoeD1zZXEoMCwxLGxlbmd0aC5vdXQ9MTAwMCkseT1zb3J0KHBpdDJzKSkpKwogIGdlb21fbGluZShjb2xvcj0nYmx1ZScsc2l6ZT0yKSsKICBnZW9tX2FibGluZSgpKwogIGxhYnMoeD0nVW5pZm9ybScseT0nUElUJykKIycKIycgUElUIHBsb3QgY29uZmlybXMgdGhlIHN1c3BpY2lvdXMuIFRoZSBjb25kaXRpb25hbCBwb3N0ZXJpb3JzIGFyZQojJyB0b28gbmFycm93LCBhbmQgdGh1cyBQSVQgdmFsdWVzIGFyZSBub3QgdW5pZm9ybWx5IGRpc3RyaWJ1dGVkLgojJyAKIycgIyA4LXNjaG9vbHMKIycKIycgTmV4dCB3ZSBpbGx1c3RyYXRlIHRoZSBwb3N0ZXJpb3IgU0JDIGluIGNhc2Ugb2YgYSBoaWVyYXJjaGljYWwKIycgbW9kZWwgd2hlcmUgYSBjZXJ0YWluIHBhcmFtZXRlcml6YXRpb24gY2FuIGxlYWQgdG8gYSBmdW5uZWwgc2hhcGVkCiMnIHBvc3RlcmlvciB0aGF0IGlzIGRpZmZpY3VsdCB0byBzYW1wbGUgd2l0aCBmaXhlZCBzdGVwIHNpemUKIycgKGR5bmFtaWMpIEhhbWlsdG9uaWFuIE1vbnRlIENhcmxvLgojJyAKIycgOC1zY2hvb2xzIGRhdGEKZGF0ID0gbGlzdChKPTgsIHk9YygyOCw4LC0zLDcsLTEsMSwxOCwxMiksIHNpZ21hPWMoMTUsMTAsMTYsMTEsOSwxMSwxMCwxOCkpCgojJyAjIyBOb24tY2VudGVyZWQgcGFyYW1ldGVyaXphdGlvbiAtIGR5bmFtaWMgSE1DCiMnCiMnIEZvciA4LXNjaG9vbHMgZGF0YSBhbmQgbW9kZWwsIGl0IGlzIGtub3duIHRoYXQgbm9uLWNlbnRlcmVkCiMnIHBhcmFtZXRlcml6YXRpb24gcHJvZHVjZXMgYSBwb3N0ZXJpb3IgdGhhdCBpcyByZWxhdGl2ZWx5IGVhc3kgdG8KIycgc2FtcGxlIHdpdGggZml4ZWQgc3RlcCBzaXplIGR5bmFtaWMgSE1DLiBXZSBleHBlY3QgdGhhdCBwb3N0ZXJpb3IKIycgU0JDIGRvZXNuJ3QgZGV0ZWN0IGFueSBwcm9ibGVtcy4KIycgCiMnIDgtc2Nob29scyBtb2RlbCB3aXRoIG5vbi1jZW50ZXJlZCBwYXJhbWV0ZXJpemF0aW9uCm1vZF9uY3AgPSBjbWRzdGFuX21vZGVsKHN0YW5fZmlsZSA9ICdzY2hvb2xzX25jcC5zdGFuJykKCiMnIHNhbXBsZSBmcm9tIHRoZSBwb3N0ZXJpb3IgZ2l2ZW4gdGhlIG9ic2VydmVkIGRhdGEKIysgd2FybmluZz1GQUxTRQpvdXQgPSBjYXB0dXJlLm91dHB1dCgKICBmaXRfbmNwIDwtIG1vZF9uY3Akc2FtcGxlKGRhdGE9ZGF0LCByZWZyZXNoPTAsIHNob3dfbWVzc2FnZXM9RkFMU0UsIHNlZWQ9MCkpCmRyYXdzX25jcCA9IGFzX2RyYXdzX3J2YXJzKHRoaW5fZHJhd3MoZml0X25jcCRkcmF3cygpLDIwKSkKdGF1X25jcCA9IGFzX2RyYXdzX21hdHJpeChzdWJzZXRfZHJhd3MoZHJhd3NfbmNwLCB2YXJpYWJsZT0idGF1IikpCiMnIGRyYXdzIGZyb20gdGhlIHBvc3RlcmlvciBwcmVkaWN0aXZlIGRpc3RyaWJ1dGlvbgp5cmVwX25jcCA9IGFzX2RyYXdzX21hdHJpeChzdWJzZXRfZHJhd3MoZHJhd3NfbmNwLCB2YXJpYWJsZT0ieXJlcCIpKQoKIycgMjAwIGl0ZXJhdGlvbnMgb2YgcG9zdGVyaW9yIFNCQwpwaXRwX25jcCA9IHRhdXBfbmNwID0gbnVtZXJpYygpCiMrIHdhcm5pbmc9RkFMU0UKZm9yIChqIGluIDE6MjAwKSB7CiAgIyBjb21iaW5lIHRoZSBvcmlnaW5hbCBkYXRhIHdpdGggcG9zdGVyaW9yIHByZWRpY3RpdmUgZGF0YQogIGRhdHAgPSBsaXN0KEogPSAyKmRhdCRKLAogICAgICAgICAgICAgIHkgPSBjKGRhdCR5LCB5cmVwX25jcFtqLF0pLAogICAgICAgICAgICAgIHNpZ21hID0gcmVwKGRhdCRzaWdtYSwgMikpCiAgIyBzYW1wbGUgZnJvbSB0aGUgc2Vjb25kIHBvc3RlcmlvcgogIG91dCA9IGNhcHR1cmUub3V0cHV0KAogICAgZml0cCA8LSBtb2RfbmNwJHNhbXBsZShkYXRhPWRhdHAsIHJlZnJlc2g9MCwgc2hvd19tZXNzYWdlcyA9IEZBTFNFLCBzZWVkPWopKQogIGRyYXdzcCA9IGFzX2RyYXdzX3J2YXJzKGZpdHAkZHJhd3MoKSkKICAjIG9uZSBkcmF3IGZyb20gdGhlIHNlY29uZCBwb3N0ZXJpb3IKICB0YXVwX25jcFtqXSA9IGFzX2RyYXdzX21hdHJpeChkcmF3c3AkdGF1KVsxXQogICMgUElUIHZhbHVlCiAgcGl0cF9uY3Bbal0gPSBtZWFuKGRyYXdzcCR0YXUgPCBhcy52ZWN0b3IodGF1X25jcFtqXSkpCn0KCmRmPWRhdGEuZnJhbWUodGF1X25jcCx0YXVwX25jcCxwaXRwX25jcCkKCmdncGxvdChkYXRhPWRmLGFlcyh4PXRhdV9uY3AseT10YXVwX25jcCkpK2dlb21fcG9pbnQoYWxwaGE9MC41LGNvbG9yPSdibHVlJykrCiAgZ2VvbV9hYmxpbmUoKSsKICBzY2FsZV94X2xvZzEwKCkrc2NhbGVfeV9sb2cxMCgpKwogIGxhYnMoeD1UZVgoJyRcXHRhdVwnIFxcc2ltIHAoXFx0YXUgfCB5X3tcXG1hdGhybXtvYnN9fSkkJykseT1UZVgoJyRcXHRhdVwnXCcgXFxzaW0gcChcXHRhdSB8IHlfaSwgeV97XFxtYXRocm17b2JzfX0pJCcpKQojJwojJyBQb3N0ZXJpb3IgZHJhd3MgYW5kIGNvbmRpdGlvbmFsIHBvc3RlcmlvciBkcmF3cyBhcmUgd2Vha2x5IGNvcnJlbGF0ZWQuCiMnIApnZ3Bsb3QoZGF0YT1kZixhZXMoeD1zb3J0KHRhdV9uY3ApLHk9c29ydCh0YXVwX25jcCkpKSsKICBnZW9tX3BvaW50KGFscGhhPS4zLGNvbG9yPSdibHVlJykrCiAgZ2VvbV9hYmxpbmUoKSsKICBzY2FsZV94X2xvZzEwKCkrc2NhbGVfeV9sb2cxMCgpKwogIGxhYnMoeD1UZVgoJ3NvcnRlZCAkXFx0YXVcJyBcXHNpbSBwKFxcdGF1IHwgeV97XFxtYXRocm17b2JzfX0pJCcpLHk9VGVYKCdzb3J0ZWQgJFxcdGF1XCdcJyBcXHNpbSBwKFxcdGF1IHwgeV9pLCB5X3tcXG1hdGhybXtvYnN9fSkkJykpCiMnCiMnIFFRLXBsb3QgbG9va3MgZ29vZC4KIycgCgpnZ3Bsb3QoZGF0YT1kZixhZXMoeD1zZXEoMCwxLGxlbmd0aC5vdXQ9MjAwKSx5PXNvcnQocGl0cF9uY3ApKSkrCiAgZ2VvbV9saW5lKGNvbG9yPSdibHVlJyxzaXplPTIpKwogIGdlb21fYWJsaW5lKCkrCiAgbGFicyh4PSdVbmlmb3JtJyx5PSdQSVQnKQojJwojJyBFQ0RGIG9mIHByb2JhYmlsaXR5IGludGVncmFsIHRyYW5zZm9ybWF0aW9uIChQSVQpIGxvb2tzIGFsc28gZ29vZAojJyBhcyB3ZSBleHBlY3RlZC4KIycgCiMnICMjIENlbnRlcmVkIHBhcmFtZXRlcml6YXRpb24gLSBkeW5hbWljIEhNQwojJwojJyBGb3IgOC1zY2hvb2xzIGRhdGEgYW5kIG1vZGVsLCBpdCBpcyBrbm93biB0aGF0IGNlbnRlcmVkCiMnIHBhcmFtZXRlcml6YXRpb24gcHJvZHVjZXMgYSBwb3N0ZXJpb3IgdGhhdCBoYXMgc3Ryb25nIGZ1bm5lbCBzaGFwZQojJyBhbmQgd2l0aCBmaXhlZCBzdGVwIHNpemUgKGR5bmFtaWMpIEhNQyBpcyB1bmFibGUgdG8gZXhwbG9yZSB0aGUKIycgbmFycm93IHBhcnQgb2YgdGhlIGZ1bm5lbC4gVGhlIEhNQyBzcGVjaWZpYyBhbmQgZ2VuZXJpYyBNQ01DCiMnIGRpYWdub3N0aWNzIGluZGljYXRlIHRoZXNlIHByb2JsZW1zLCBhbmQgdGh1cyBwb3N0ZXJpb3IgU0JDIGlzIG5vdAojJyBuZWNlc3NhcnkgaGVyZSwgYnV0IGFzIGEgd2VsbCBrbm93biBleGFtcGxlIDgtc2Nob29scyBjZW50ZXJlZAojJyBwYXJhbWV0ZXJpemF0aW9uIHdvcmtzIGFzIGEgdXNlZnVsIGlsbHVzdHJhdGlvbi4KIycgCiMnIDgtc2Nob29scyBtb2RlbCB3aXRoIGNlbnRlcmVkIHBhcmFtZXRlcml6YXRpb24gbW9kZWwKbW9kX2NwID0gY21kc3Rhbl9tb2RlbChzdGFuX2ZpbGUgPSAnc2Nob29sc19jcC5zdGFuJykKCiMnIHNhbXBsZSBmcm9tIHRoZSBwb3N0ZXJpb3IgZ2l2ZW4gdGhlIG9ic2VydmVkIGRhdGEKb3V0ID0gY2FwdHVyZS5vdXRwdXQoCiAgZml0X2NwIDwtIG1vZF9jcCRzYW1wbGUoZGF0YT1kYXQsIHJlZnJlc2g9MCwgc2hvd19tZXNzYWdlcz1GQUxTRSwgc2VlZD0wKSkKZHJhd3NfY3AgPSBhc19kcmF3c19ydmFycyh0aGluX2RyYXdzKGZpdF9jcCRkcmF3cygpLDIwKSkKdGF1X2NwID0gYXNfZHJhd3NfbWF0cml4KHN1YnNldF9kcmF3cyhkcmF3c19jcCwgdmFyaWFibGU9InRhdSIpKQojJyBkcmF3cyBmcm9tIHRoZSBwb3N0ZXJpb3IgcHJlZGljdGl2ZSBkaXN0cmlidXRpb24KeXJlcF9jcCA9IGFzX2RyYXdzX21hdHJpeChzdWJzZXRfZHJhd3MoZHJhd3NfY3AsIHZhcmlhYmxlPSJ5cmVwIikpCgojJyAyMDAgaXRlcmF0aW9ucyBvZiBwb3N0ZXJpb3IgU0JDCnBpdHBfY3AgPSB0YXVwX2NwID0gbnVtZXJpYygpCiMrIHdhcm5pbmc9RkFMU0UKZm9yIChqIGluIDE6MjAwKSB7CiAgIyBjb21iaW5lIHRoZSBvcmlnaW5hbCBkYXRhIHdpdGggcG9zdGVyaW9yIHByZWRpY3RpdmUgZGF0YQogIGRhdHAgPSBsaXN0KEogPSAyKmRhdCRKLAogICAgICAgICAgICAgIHkgPSBjKGRhdCR5LCB5cmVwX2NwW2osXSksCiAgICAgICAgICAgICAgc2lnbWEgPSByZXAoZGF0JHNpZ21hLCAyKSkKICAjIHNhbXBsZSBmcm9tIHRoZSBzZWNvbmQgcG9zdGVyaW9yCiAgb3V0ID0gY2FwdHVyZS5vdXRwdXQoCiAgICBmaXRwIDwtIG1vZF9jcCRzYW1wbGUoZGF0YT1kYXRwLCByZWZyZXNoPTAsIHNob3dfbWVzc2FnZXMgPSBGQUxTRSwgc2VlZD1qKSkKICBkcmF3c3AgPSBhc19kcmF3c19ydmFycyhmaXRwJGRyYXdzKCkpCiAgIyBvbmUgZHJhdyBmcm9tIHRoZSBzZWNvbmQgcG9zdGVyaW9yCiAgdGF1cF9jcFtqXSA9IGFzX2RyYXdzX21hdHJpeChkcmF3c3AkdGF1KVsxXQogICMgUElUIHZhbHVlCiAgcGl0cF9jcFtqXSA9IG1lYW4oZHJhd3NwJHRhdSA8IGFzLnZlY3Rvcih0YXVfY3Bbal0pKQp9CgpkZj1kYXRhLmZyYW1lKHRhdV9jcCx0YXVwX2NwLHBpdHBfY3ApCgpwMj1nZ3Bsb3QoZGF0YT1kZixhZXMoeD10YXVfY3AseT10YXVwX2NwKSkrCiAgZ2VvbV9wb2ludChhbHBoYT0wLjUsY29sb3I9J2JsdWUnKSsKICBnZW9tX2FibGluZSgpKwogIHNjYWxlX3hfbG9nMTAoKSsKICBzY2FsZV95X2xvZzEwKCkrCiAgbGFicyh4PVRlWCgnJFxcdGF1XCcgXFxzaW0gcChcXHRhdSB8IHlfe1xcbWF0aHJte29ic319KSQnKSx5PVRlWCgnJFxcdGF1XCdcJyBcXHNpbSBwKFxcdGF1IHwgeV9pLCB5X3tcXG1hdGhybXtvYnN9fSkkJykpCnBsaW1zID0gcmFuZ2UoYyhnZ3Bsb3RfYnVpbGQocDIpJGxheW91dCRwYW5lbF9wYXJhbXNbWzFdXSR4LnJhbmdlLAogICAgICAgICAgICAgICAgIGdncGxvdF9idWlsZChwMikkbGF5b3V0JHBhbmVsX3BhcmFtc1tbMV1dJHkucmFuZ2UpKQpwMitzY2FsZV94X2xvZzEwKGxpbWl0cz0xMF5wbGltcykrCiAgc2NhbGVfeV9sb2cxMChsaW1pdHM9MTBecGxpbXMpCiMnCiMnIFBvc3RlcmlvciBkcmF3cyBhbmQgY29uZGl0aW9uYWwgcG9zdGVyaW9yIGRyYXdzIGFyZSB3ZWFrbHkKIycgY29ycmVsYXRlZC4gSXQgaXMgZGlmZmljdWx0IHRvIHNlZSBhbnkgZGlzY3JlcGFuY3kgaW4gdGhpcyBwbG90LgojJyAKZ2dwbG90KGRhdGE9ZGYsYWVzKHg9c29ydCh0YXVfY3ApLHk9c29ydCh0YXVwX2NwKSkpKwogIGdlb21fcG9pbnQoYWxwaGE9LjMsY29sb3I9J2JsdWUnKSsKICBnZW9tX2FibGluZSgpKwogIHNjYWxlX3hfbG9nMTAoKSsKICBzY2FsZV95X2xvZzEwKCkrCiAgbGFicyh4PVRlWCgnc29ydGVkICRcXHRhdVwnIFxcc2ltIHAoXFx0YXUgfCB5X3tcXG1hdGhybXtvYnN9fSkkJykseT1UZVgoJ3NvcnRlZCAkXFx0YXVcJ1wnIFxcc2ltIHAoXFx0YXUgfCB5X2ksIHlfe1xcbWF0aHJte29ic319KSQnKSkKIycKIycgUVEtcGxvdCByZXZlYWxzIGNsZWFyIGRpc2NyZXBhbmN5IGluIHNtYWxsIHZhbHVlcyBvZiAkXHRhdSQuIEhlcmUKIycgd2UgZG8gZ2V0IHNvbWV0aW1lcyBtdWNoIHNtYWxsZXIgY29uZGl0aW9uYWwgcG9zdGVyaW9yIGRyYXdzIHRoYW4KIycgdGhlIHNtYWxsZXN0IG9yaWdpbmFsIHBvc3RlcmlvciBkcmF3cywgd2hpY2ggaW5kaWNhdGVzIHRoYXQgdGhlCiMnIGluZmVyZW5jZSBmb3IgdGhlIG9yaWdpbmFsIHBvc3RlcmlvciBpcyBmYWlsaW5nLgojJyAKZ2dwbG90KGRhdGE9ZGYsYWVzKHg9c2VxKDAsMSxsZW5ndGgub3V0PTIwMCkseT1zb3J0KHBpdHBfY3ApKSkrCiAgZ2VvbV9saW5lKGNvbG9yPSdibHVlJyxzaXplPTIpKwogIGdlb21fYWJsaW5lKCkrCiAgbGFicyh4PSdVbmlmb3JtJyx5PSdQSVQnKQojJwojJyBQSVQgcGxvdCBkb2Vzbid0IHNob3cgdGhlIGRpc2NyZXBhbmN5IHRoYXQgY2xlYXJseSwgYWx0aG91Z2ggdGhlcmUKIycgaXMgc29tZSBzdXNwaWNpb24gaW4gdGhlIHNtYWxsIHZhbHVlcy4KIycgCiMnICMjIE5vbi1jZW50ZXJlZCBwYXJhbWV0ZXJpemF0aW9uIC0gQURWSQojJwojJyBBdXRvbWF0aWMgZGlmZmVyZW50aWF0aW9uIHZhcmlhdGlvbmFsIGluZmVyZW5jZSB1c2VzIG5vcm1hbAojJyBhcHByb3hpbWF0aW9uLiBAWWFvK1ZlaHRhcmkrU2ltcHNvbitHZWxtYW46MjAxOCBkZW1vbnN0cmF0ZSB0aGF0CiMnIChnaXZlbiBlbm91Z2ggY29tcHV0YXRpb24gdGltZSkgaXQgd29ya3MgcmVhc29uYWJseSBmb3IgdGhlCiMnIG5vbi1jZW50ZXJlZCBwYXJhbWV0ZXJpemF0aW9uLgojJyAKIycgOC1zY2hvb2xzIG1vZGVsIHdpdGggbm9uLWNlbnRlcmVkIHBhcmFtZXRlcml6YXRpb24KbW9kX25jcCA9IGNtZHN0YW5fbW9kZWwoc3Rhbl9maWxlID0gJ3NjaG9vbHNfbmNwLnN0YW4nKQoKIycgc2FtcGxlIGZyb20gdGhlIHBvc3RlcmlvciBnaXZlbiB0aGUgb2JzZXJ2ZWQgZGF0YQojKyB3YXJuaW5nPUZBTFNFCm91dCA9IGNhcHR1cmUub3V0cHV0KAogIGZpdF9uY3B2IDwtIG1vZF9uY3AkdmFyaWF0aW9uYWwoZGF0YT1kYXQsIHJlZnJlc2g9MCwgc2VlZD0wLCB0b2xfcmVsX29iaj0xZS00LCBpdGVyPTFlNSkpCmRyYXdzX25jcHYgPSBhc19kcmF3c19ydmFycyh0aGluX2RyYXdzKGZpdF9uY3B2JGRyYXdzKCksNSkpCnRhdV9uY3B2ID0gYXNfZHJhd3NfbWF0cml4KHN1YnNldF9kcmF3cyhkcmF3c19uY3B2LCB2YXJpYWJsZT0idGF1IikpCiMnIGRyYXdzIGZyb20gdGhlIHBvc3RlcmlvciBwcmVkaWN0aXZlIGRpc3RyaWJ1dGlvbgp5cmVwX25jcHYgPSBhc19kcmF3c19tYXRyaXgoc3Vic2V0X2RyYXdzKGRyYXdzX25jcHYsIHZhcmlhYmxlPSJ5cmVwIikpCgojJyAyMDAgaXRlcmF0aW9ucyBvZiBwb3N0ZXJpb3IgU0JDCnBpdHBfbmNwdiA9IHRhdXBfbmNwdiA9IG51bWVyaWMoKQojKyB3YXJuaW5nPUZBTFNFCmZvciAoaiBpbiAxOjIwMCkgewogICMgY29tYmluZSB0aGUgb3JpZ2luYWwgZGF0YSB3aXRoIHBvc3RlcmlvciBwcmVkaWN0aXZlIGRhdGEKICBkYXRwID0gbGlzdChKID0gMipkYXQkSiwKICAgICAgICAgICAgICB5ID0gYyhkYXQkeSwgeXJlcF9uY3B2W2osXSksCiAgICAgICAgICAgICAgc2lnbWEgPSByZXAoZGF0JHNpZ21hLCAyKSkKICAjIHNhbXBsZSBmcm9tIHRoZSBzZWNvbmQgcG9zdGVyaW9yCiAgb3V0ID0gY2FwdHVyZS5vdXRwdXQoCiAgICBmaXRwIDwtIG1vZF9uY3AkdmFyaWF0aW9uYWwoZGF0YT1kYXRwLCByZWZyZXNoPTAsIHNlZWQ9aiwgdG9sX3JlbF9vYmo9MWUtNCwgaXRlcj0xZTUpKQogIGRyYXdzcCA9IGFzX2RyYXdzX3J2YXJzKGZpdHAkZHJhd3MoKSkKICAjIG9uZSBkcmF3IGZyb20gdGhlIHNlY29uZCBwb3N0ZXJpb3IKICB0YXVwX25jcHZbal0gPSBhc19kcmF3c19tYXRyaXgoZHJhd3NwJHRhdSlbMV0KICAjIFBJVCB2YWx1ZQogIHBpdHBfbmNwdltqXSA9IG1lYW4oZHJhd3NwJHRhdSA8IGFzLnZlY3Rvcih0YXVfbmNwdltqXSkpCn0KCmRmPWRhdGEuZnJhbWUodGF1X25jcHYsdGF1cF9uY3B2LHBpdHBfbmNwdikKCnAyPWdncGxvdChkYXRhPWRmLGFlcyh4PXRhdV9uY3B2LHk9dGF1cF9uY3B2KSkrCiAgZ2VvbV9wb2ludChhbHBoYT0wLjUsY29sb3I9J2JsdWUnKSsKICBnZW9tX2FibGluZSgpKwogIHNjYWxlX3hfbG9nMTAoKSsKICBzY2FsZV95X2xvZzEwKCkrCiAgbGFicyh4PVRlWCgnJFxcdGF1XCcgXFxzaW0gcChcXHRhdSB8IHlfe1xcbWF0aHJte29ic319KSQnKSx5PVRlWCgnJFxcdGF1XCdcJyBcXHNpbSBwKFxcdGF1IHwgeV9pLCB5X3tcXG1hdGhybXtvYnN9fSkkJykpCnBsaW1zID0gcmFuZ2UoYyhnZ3Bsb3RfYnVpbGQocDIpJGxheW91dCRwYW5lbF9wYXJhbXNbWzFdXSR4LnJhbmdlLAogICAgICAgICAgICAgICAgIGdncGxvdF9idWlsZChwMikkbGF5b3V0JHBhbmVsX3BhcmFtc1tbMV1dJHkucmFuZ2UpKQpwMitzY2FsZV94X2xvZzEwKGxpbWl0cz0xMF5wbGltcykrCiAgc2NhbGVfeV9sb2cxMChsaW1pdHM9MTBecGxpbXMpCiMnCiMnIFBvc3RlcmlvciBkcmF3cyBhbmQgY29uZGl0aW9uYWwgcG9zdGVyaW9yIGRyYXdzIGFyZSB3ZWFrbHkKIycgY29ycmVsYXRlZC4gSXQgaXMgZGlmZmljdWx0IHRvIHNlZSBhbnkgZGlzY3JlcGFuY3kgaW4gdGhpcyBwbG90LgojJyAKZ2dwbG90KGRhdGE9ZGYsYWVzKHg9c29ydCh0YXVfbmNwdikseT1zb3J0KHRhdXBfbmNwdikpKSsKICBnZW9tX3BvaW50KGFscGhhPS4zLGNvbG9yPSdibHVlJykrCiAgZ2VvbV9hYmxpbmUoKSsKICBzY2FsZV94X2xvZzEwKCkrCiAgc2NhbGVfeV9sb2cxMCgpKwogIGxhYnMoeD1UZVgoJ3NvcnRlZCAkXFx0YXVcJyBcXHNpbSBwKFxcdGF1IHwgeV97XFxtYXRocm17b2JzfX0pJCcpLHk9VGVYKCdzb3J0ZWQgJFxcdGF1XCdcJyBcXHNpbSBwKFxcdGF1IHwgeV9pLCB5X3tcXG1hdGhybXtvYnN9fSkkJykpCiMnCiMnIFFRLXBsb3QgaW5kaWNhdGVzIHRoYXQgdGhlIG9yaWdpbmFsIHBvc3RlcmlvciBpcyBsaWtlbHkgdG8gYmUKIycgbmFycm93ZXIgdGhhbiB0aGUgdHJ1ZSBwb3N0ZXJpb3IuCiMnIApnZ3Bsb3QoZGF0YT1kZixhZXMoeD1zZXEoMCwxLGxlbmd0aC5vdXQ9MjAwKSx5PXNvcnQocGl0cF9uY3B2KSkpKwogIGdlb21fbGluZShjb2xvcj0nYmx1ZScsc2l6ZT0yKSsKICBnZW9tX2FibGluZSgpKwogIGxhYnMoeD0nVW5pZm9ybScseT0nUElUJykKIycKIycgUElUIHBsb3QgaW5kaWNhdGVzIHByb2JsZW1zIGluIHRoZSBleHRyZW1lIGxlZnQgdGFpbC4KIycgCiMnICMjIENlbnRlcmVkIHBhcmFtZXRlcml6YXRpb24gLSBBRFZJCiMnIAojJyA4LXNjaG9vbHMgbW9kZWwgd2l0aCBjZW50ZXJlZCBwYXJhbWV0ZXJpemF0aW9uIG1vZGVsCm1vZF9jcCA9IGNtZHN0YW5fbW9kZWwoc3Rhbl9maWxlID0gJ3NjaG9vbHNfY3Auc3RhbicpCgojJyBzYW1wbGUgZnJvbSB0aGUgcG9zdGVyaW9yIGdpdmVuIHRoZSBvYnNlcnZlZCBkYXRhCm91dCA9IGNhcHR1cmUub3V0cHV0KAogIGZpdF9jcHYgPC0gbW9kX2NwJHZhcmlhdGlvbmFsKGRhdGE9ZGF0LCByZWZyZXNoPTAsIHNlZWQ9MCwgdG9sX3JlbF9vYmo9MWUtNCwgaXRlcj0xZTUpKQpkcmF3c19jcHYgPSBhc19kcmF3c19ydmFycyh0aGluX2RyYXdzKGZpdF9jcHYkZHJhd3MoKSw1KSkKdGF1X2NwdiA9IGFzX2RyYXdzX21hdHJpeChzdWJzZXRfZHJhd3MoZHJhd3NfY3B2LCB2YXJpYWJsZT0idGF1IikpCiMnIGRyYXdzIGZyb20gdGhlIHBvc3RlcmlvciBwcmVkaWN0aXZlIGRpc3RyaWJ1dGlvbgp5cmVwX2NwdiA9IGFzX2RyYXdzX21hdHJpeChzdWJzZXRfZHJhd3MoZHJhd3NfY3B2LCB2YXJpYWJsZT0ieXJlcCIpKQoKIycgMjAwIGl0ZXJhdGlvbnMgb2YgcG9zdGVyaW9yIFNCQwpwaXRwX2NwdiA9IHRhdXBfY3B2ID0gbnVtZXJpYygpCiMrIHdhcm5pbmc9RkFMU0UKZm9yIChqIGluIDE6MjAwKSB7CiAgIyBjb21iaW5lIHRoZSBvcmlnaW5hbCBkYXRhIHdpdGggcG9zdGVyaW9yIHByZWRpY3RpdmUgZGF0YQogIGRhdHAgPSBsaXN0KEogPSAyKmRhdCRKLAogICAgICAgICAgICAgIHkgPSBjKGRhdCR5LCB5cmVwX2NwdltqLF0pLAogICAgICAgICAgICAgIHNpZ21hID0gcmVwKGRhdCRzaWdtYSwgMikpCiAgIyBzYW1wbGUgZnJvbSB0aGUgc2Vjb25kIHBvc3RlcmlvcgogIG91dCA9IGNhcHR1cmUub3V0cHV0KAogICAgZml0cCA8LSBtb2RfY3AkdmFyaWF0aW9uYWwoZGF0YT1kYXRwLCByZWZyZXNoPTAsIHNlZWQ9MjAwK2osIHRvbF9yZWxfb2JqPTFlLTQsIGl0ZXI9MWU1KSkKICBkcmF3c3AgPSBhc19kcmF3c19ydmFycyhmaXRwJGRyYXdzKCkpCiAgIyBvbmUgZHJhdyBmcm9tIHRoZSBzZWNvbmQgcG9zdGVyaW9yCiAgdGF1cF9jcHZbal0gPSBhc19kcmF3c19tYXRyaXgoZHJhd3NwJHRhdSlbMV0KICAjIFBJVCB2YWx1ZQogIHBpdHBfY3B2W2pdID0gbWVhbihkcmF3c3AkdGF1IDwgYXMudmVjdG9yKHRhdV9jcHZbal0pKQp9CgpkZj1kYXRhLmZyYW1lKHRhdV9jcHYsdGF1cF9jcHYscGl0cF9jcHYpCgpwMj1nZ3Bsb3QoZGF0YT1kZixhZXMoeD10YXVfY3B2LHk9dGF1cF9jcHYpKSsKICBnZW9tX3BvaW50KGFscGhhPTAuNSxjb2xvcj0nYmx1ZScpKwogIGdlb21fYWJsaW5lKCkrCiAgc2NhbGVfeF9sb2cxMCgpKwogIHNjYWxlX3lfbG9nMTAoKSsKICBsYWJzKHg9VGVYKCckXFx0YXVcJyBcXHNpbSBwKFxcdGF1IHwgeV97XFxtYXRocm17b2JzfX0pJCcpLHk9VGVYKCckXFx0YXVcJ1wnIFxcc2ltIHAoXFx0YXUgfCB5X2ksIHlfe1xcbWF0aHJte29ic319KSQnKSkKcGxpbXMgPSByYW5nZShjKGdncGxvdF9idWlsZChwMikkbGF5b3V0JHBhbmVsX3BhcmFtc1tbMV1dJHgucmFuZ2UsCiAgICAgICAgICAgICAgICAgZ2dwbG90X2J1aWxkKHAyKSRsYXlvdXQkcGFuZWxfcGFyYW1zW1sxXV0keS5yYW5nZSkpCnAyK3NjYWxlX3hfbG9nMTAobGltaXRzPTEwXnBsaW1zKSsKICBzY2FsZV95X2xvZzEwKGxpbWl0cz0xMF5wbGltcykKIycKIycgUG9zdGVyaW9yIGRyYXdzIGFuZCBjb25kaXRpb25hbCBwb3N0ZXJpb3IgZHJhd3MgYXJlIHdlYWtseQojJyBjb3JyZWxhdGVkLiBJdCBpcyBkaWZmaWN1bHQgdG8gc2VlIGFueSBkaXNjcmVwYW5jeSBpbiB0aGlzIHBsb3QuCiMnIApnZ3Bsb3QoZGF0YT1kZixhZXMoeD1zb3J0KHRhdV9jcHYpLHk9c29ydCh0YXVwX2NwdikpKSsKICBnZW9tX3BvaW50KGFscGhhPS4zLGNvbG9yPSdibHVlJykrCiAgZ2VvbV9hYmxpbmUoKSsKICBzY2FsZV94X2xvZzEwKCkrCiAgc2NhbGVfeV9sb2cxMCgpKwogIGxhYnMoeD1UZVgoJ3NvcnRlZCAkXFx0YXVcJyBcXHNpbSBwKFxcdGF1IHwgeV97XFxtYXRocm17b2JzfX0pJCcpLHk9VGVYKCdzb3J0ZWQgJFxcdGF1XCdcJyBcXHNpbSBwKFxcdGF1IHwgeV9pLCB5X3tcXG1hdGhybXtvYnN9fSkkJykpCiMnCiMnIFFRLXBsb3QgaGFzIHNvbWUgc3RydWN0dXJlLCBidXQgbm8gY2xlYXIgaW5kaWNhdGlvbiBvZiB0aGUKIycgcHJvYmxlbXMuCiMnIApnZ3Bsb3QoZGF0YT1kZixhZXMoeD1zZXEoMCwxLGxlbmd0aC5vdXQ9MjAwKSx5PXNvcnQocGl0cF9jcHYpKSkrCiAgZ2VvbV9saW5lKGNvbG9yPSdibHVlJyxzaXplPTIpKwogIGdlb21fYWJsaW5lKCkrCiAgbGFicyh4PSdVbmlmb3JtJyx5PSdQSVQnKQojJwojJyBQSVQgcGxvdCBzaG93cyBjbGVhcmx5IHRoYXQgdGhlIHBvc3RlcmlvciB2YXJpYW5jZSBpcyB1bmRlcmVzdGltYXRlZC4KIycKIycgIyMgQ29tcGFyaXNvbiBvZiBhcHByb3hpbWF0aW9ucwojJwojJyBBZnRlciBzZWVpbmcgdGhlIGRpYWdub3N0aWNzLCB3ZSBjb21wYXJlIGFsbCBwb3N0ZXJpb3IKIycgYXBwcm94aW1hdGlvbnMgYW5kIHRoZSBjb25kaXRpb25hbCBwb3N0ZXJpb3JzLgojJyAKcnRhdT1hc19kcmF3c19kZihydmFyKGNiaW5kKG5jcD1hcy52ZWN0b3IodGF1X25jcCkscG5jcD10YXVwX25jcCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNwPWFzLnZlY3Rvcih0YXVfY3ApLHBjcD10YXVwX2NwLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgbmNwdj1hcy52ZWN0b3IodGF1X25jcHYpLHBuY3B2PXRhdXBfbmNwdiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNwdj1hcy52ZWN0b3IodGF1X2NwdikscGNwdj10YXVwX2NwdikpKQpydGF1PC1yZW5hbWVfdmFyaWFibGVzKHJ0YXUsCiAgICAgICAgICAgICAgICAgICAgICAgIk5vbi1jZW50ZXJlZCBITUMiPSd4W25jcF0nLAogICAgICAgICAgICAgICAgICAgICAgICJOb24tY2VudGVyZWQgSE1DLVNCQyI9J3hbcG5jcF0nLAogICAgICAgICAgICAgICAgICAgICAgICJDZW50ZXJlZCBITUMiPSd4W2NwXScsCiAgICAgICAgICAgICAgICAgICAgICAgIkNlbnRlcmVkIEhNQy1TQkMiPSd4W3BjcF0nLAogICAgICAgICAgICAgICAgICAgICAgICJOb24tY2VudGVyZWQgQURWSSI9J3hbbmNwdl0nLAogICAgICAgICAgICAgICAgICAgICAgICJOb24tY2VudGVyZWQgQURWSS1TQkMiPSd4W3BuY3B2XScsCiAgICAgICAgICAgICAgICAgICAgICAgIkNlbnRlcmVkIEFEVkkiPSd4W2Nwdl0nLAogICAgICAgICAgICAgICAgICAgICAgICJDZW50ZXJlZCBBRFZJLVNCQyI9J3hbcGNwdl0nKQptY21jX2FyZWFzKGFzX2RyYXdzX21hdHJpeChsb2cocnRhdSkpKQojJwojJyBXZSBzZWUgdGhhdAojJyAKIycgLSBub24tY2VudGVyZWQgSE1DIG1hdGNoZXMgbm9uLWNlbnRlcmVkIEhNQy1TQkMKIycgLSBjZW50ZXJlZCBITUMgaXMgbWlzc2luZyBzbWFsbGVyIHZhbHVlcyBvZiB0YXUsIHdoaWNoIGlzIHJldmVhbGVkCiMnICAgYnkgY2VudGVyZWQgSE1DLVNCQwojJyAtIG5vbi1jZW50ZXJlZCBBRFZJIGlzIGNsb3NlIHRvIG5vbi1jZW50ZXJlZCBITUMtU0JDLiBUaGUgQURWSQojJyAgIG5vcm1hbCBhcHByb3hpbWF0aW9uIGhhcyBtb3N0IG9mIHRoZSBtYXNzIHdoZXJlIHRoZSB0cnVlCiMnICAgcG9zdGVyaW9yIChiYXNlZCBvbiBub24tY2VudGVyZWQgSE1DKSwgYnV0IHRoZSBub3JtYWwKIycgICBhcHByb3hpbWF0aW9uIGlzIG1pc3NpbmcgdGhlIHNrZXduZXNzIG9mIHRoZSB0cnVlIHBvc3RlcmlvciBhbmQKIycgICB0aGlzIHdhcyBub3QgaW5kaWNhdGVkIGJ5IHRoZSBwb3N0ZXJpb3IgU0JDLgojJyAtIENlbnRlcmVkIEFEVkkgbG9va3Mgc2ltaWxhciB0byBjZW50ZXJlZCBITUMtU0JDLiBUaGUgQURWSSBub3JtYWwKIycgICBhcHByb3hpbWF0aW9uIGlzIHZlcnkgZGlmZmVyZW50IGZyb20gdGhlIHRydWUgcG9zdGVyaW9yIChiYXNlZCBvbgojJyAgIG5vbi1jZW50ZXJlZCBITUMpLCBhbmQgdGhlIHBvc3RlcmlvciBTQkMgZGlkIGluZGljYXRlIHNldmVyZQojJyAgIHVuZGVyZXN0aW1hdGlvbiBvZiB0aGUgcG9zdGVyaW9yIHZhcmlhbmNlLgojJwojJyA8YnIgLz4KIycgCiMnICMgUmVmZXJlbmNlcyB7LnVubnVtYmVyZWR9CiMnIAojJyA8ZGl2IGlkPSJyZWZzIj48L2Rpdj4KIycgCiMnICMgTGljZW5zZXMgey51bm51bWJlcmVkfQojJyAKIycgKiBDb2RlICZjb3B5OyAyMDIyLCBBa2kgVmVodGFyaSwgbGljZW5zZWQgdW5kZXIgQlNELTMuCiMnICogVGV4dCAmY29weTsgMjAyMiwgQWtpIFZlaHRhcmksIGxpY2Vuc2VkIHVuZGVyIENDLUJZLU5DIDQuMC4KIycgCiMnICMgT3JpZ2luYWwgQ29tcHV0aW5nIEVudmlyb25tZW50IHsudW5udW1iZXJlZH0KIycgCnNlc3Npb25JbmZvKCkKIycgCiMnIDxiciAvPgo=